Page 7 - 6449

Виробництво цих видів продукції може здійснюватися лише за
умови, що сумарна витрата сировини кожного типу не може перевищувати
наявні запаси, що з математичного зору може бути записано у вигляді
системи нерівностей
n
a x  a x  ...  a x   a x  b =і 1, … , m. (1.2)
i1 1 i2 2 in n ij j i,
 j 1
Крім того, величини x j ,  1, , n повинні задовольняти очевидній
j
умові:
x  . 0 (1.3)
j
Таким чином, можна сформулювати наступну задачу: знайти
максимум функції Z , заданої співвідношенням (1.1) за умов (1.2) та (1.3).
Поставлена таким чином задача називається задачею лінійного
програмування [5,9,17], оскільки всі функції, що входять в співвідношення
(1.1)-(1.3) є лінійними функціями аргументів x .
j
Слід зазначити, що при постановці задачі, та її формалізації ми
вибирали найпростіші випадки (незмінність в часі величини b , c , a ), а
i i ij
здійснена постановка задачі є досить загальною, тому ми не деталізували,
яка саме фірма розглядається, яку продукцію вона виготовляє, як
формується матриця a – в цьому проявляється відома властивість
ij
мистецтва математики – можливість різні речі та об’єкти називати
однаковими іменами.
Розглянемо деякі основні поняття теорії лінійного програмування.
Функція Z , як задається співвідношенням (1.1) називається цільовою
функцією задачі, вектор с с ( 1 ,..., с n )називається вектором прибутку;
вектор (b b 1 ,..., b m ) – вектором обмежень, A – матриця {a ij }називається

матрицею витрат, вектор (х х 1 ,..., х n )називається вектором стратегій, в
переважній більшості задач цей вектор має невід’ємні компоненти: x  .
0
j
Таким чином, задача лінійного програмування може ставитися у
спрощеній матричній формі: знайти
Z  c  x  max, min, (1.4)
за умови:
A x  x , b  . 0 (1.5)
Форма запису (1.4)-(1.5) дозволяє компактно записати умову

задачі, але не дозволяє одержати її розв’язок.
Якщо компоненти вектора х ( х 1 ,..., х n ) задовольняють систему
обмежень (1.2) (або (1.5)), то кажуть, що вектор х є допустимим
розв’язком задачі.
Якщо допустимий розв’язок задачі (х х j ,..., х n ) доставляє екстремум

функції Z , заданій співвідношенням (1.1), то він називається оптимальним
розв’язком задачі.

7