span>
ГЇ а 21 x 1 + а 22 x 2 + ... + а 2n x n = b 2
(I) Г ........................
Г® а m1 x 1 + а m ВІ x 2 + ... + а mn x n = b m
і лінійна функція | = c 1 x 1 + c 2 x 2 + ... + c n x n (II) .
Потрібно знайти такі невід'ємні рішення х 1 ? 0, х 2 ? 0 ... х n ? 0 (III) системи (I) при яких функція? приймає найменше (найбільше) значення.
Рівняння (I) називаються обмеженнями даного завдання, рівняння (II) називається лінійною формою, а рівняння (III), строго кажучи, теж є обмеженнями, проте їх не прийнято так називати, оскільки вони є загальними для всіх завдань лінійного програмування, а не тільки конкретного завдання. Будь-яке невід'ємне рішення системи рівнянь називається допустимим. Допустиме рішення, що дає мінімум функції?, Оптимальне рішення (якщо воно існує) не обов'язково єдино; можливі випадки, коли є незліченна безліч оптимальних рішень. Нарешті, саму функцію? часто називають лінійною формою або функцією мети.
Здавалося б, тому що задача лінійного програмування ставиться як завдання мінімізації деякої функції?, то можна застосувати класичний прийом диференціального числення....
