розглянутий метод розв'язання задач лінійного програмування. br/>В
I. ТЕОРЕТИЧНИЙ РОЗДІЛ
В
1.1 Лінійне програмування
Лінійне програмування - математична дисципліна, присвячена теорії і методам вирішення завдань про екстремуму лінійних функцій на множинах n-мірного векторного простору, задаються системами лінійних рівнянь і нерівностей.
Лінійне програмування є окремим випадком математичного програмування. Одночасно воно - основа декількох методів вирішення завдань цілочисельного і нелінійного програмування.
Багато властивостей завдань лінійного програмування можна інтерпретувати також як властивості багатогранників і таким чином геометрично формулювати і доводити їх.
Термін В«програмуванняВ» потрібно розуміти в сенсі В«плануванняВ». Він був запропонований в середині 1940-х років Джорджем Данцигом, одним із засновників лінійного програмування, ще до того, як комп'ютери були використані для вирішення лінійних задач оптимізації.
Математичне формулювання задачі лінійного програмування
В
Потрібно максимізувати
В
за умов при i = 0, 1, 2,. . . , M. p> Іноді на x i також накладається деякий набір обмежень у вигляді рівностей, але від них можна позбутися, послідовно висловлюючи одну змінну через інші і підставляючи її у всіх інших равенствах і нерівностях (а також у функції f).
Таке завдання називають "основний" або "стандартної" в лінійному програмуванні.
В
1.2 Формулювання завдання
Дано лінійна функція Z = С 1 х 1 + С 2 х 2 + ... + С N x N (1.1)
і система лінійних обмежень
a 11 x 1 + a 22 x 2 + ... + A 1N Х N = b 1
a 21 x 1 + A 22 x 2 + ... + A 2N Х N = b 2
. . . . . . . . . . . . . . . p> a i1 x 1 + A i2 x 2 + ... + A iN Х N = b i (1.2). . . . . . . . . . . . . . . p> a M1 x 1 + A M2 x 2 + ... + A MN Х N = b M
x j 0 (J = 1, 2, ..., n) (1.3)
де а ij , b j і С j - задані постійні величини.
Знайти такі невід'ємні значення х 1 , х 2 , ..., х n , які задовольняють системі обмежень (1.2) і доставляють лінійної функції (1.1) мінімальне значення.
Загальна задача має кілька форм запису. p> Векторна форма запису. Мінімізувати лінійну функцію Z = СХ при обмеженнях А 1 х 1 + А 2 x 2 + ... + А
