sub> 2 + 0,2 х 3 Ві 0,2;
0,5 х 1 + 0,6 х 2 + 0,1 х 3 Ві 0,4;
0,1 х 1 + 0,1 х 2 + 0,1 х 3 Ві 0,1;
х и Ві 0.
Оптимальний план х * = (0; 0,6; 0,4); Z * = 2,4.
В
Тема 2. Загальна завдання лінійного програмування та деякі з методів ее розв'язування
У загально вігляді розв'язання задачі математичного програмування почти Неможливо. Найдосконало вівчені задачі лінійного програмування. Це пояснюється тим, что більшість реальних Економічних моделей зводіться до задачі лінійного програмування, внаслідок чого и методи розв'язку завдань лінійного програмування найбільш розвінені.
загально задачею лінійного програмування звет завдання знаходження максимального (мінімального) значення Функції
n
Z = S C j ' X j ,
j = 1
( Z = С 0 + С 1 Х 1 + З 2 Х 2 +. . . + З n Х n );
За умів функціональніх обмежень:
n
S a ij x j ВЈ b i , де і = 1,2,. . . , K;
j = 1
а 11 х 1 + А 12 х 2 +. . . + A 1 n x n ВЈ b 1 ,
а 21 х 1 + А 22 х 2 +. . . + A 2 n x n ВЈ b 2 ,
а k1 х 1 + А k2 х 2 +. . . + A kn x n ВЈ b k ,
n
S a ij x j = b i , де і = k +1, k + 2,. . . , M;
j = 1
В
a k +1; 1 x 1 + A k +1; 2 x 2 +. . . + A k +1; n x n = b k +1 ,
a k +2; 1 x 1 + A k +2; 2 x 2 +. . . + A k +2; n x n = b k +2 ,
a m; 1 x 1 + A m; 2 x 2 +. . . + A m; n x n = b m
нефункціональніх обмежень:
x j Ві 0, де j = 1,2,3,. . . n;
а такоже a ij ; b i ; c j - задані постійні величини, а ще k ВЈ m.
Цільову функцію Можливо оптимізувати на "max", або на "min" - Це не є принципова, бо у точці х * функція Z = f (x *) - досягає мінімуму, а функція Z = - f (x *) - досягає максимуму. Таким чином мі всегда Можемо мінімізуваті цільову функцію, що не втрачаючі загальності підходу.
Цільова функція та УСІ функціональні обмеження , як ми Вже бачили, мают лінійну форму відносно невідоміх x j , что и Дає Цій задачі математичного програмування Назва - Лінійне програмування.
Невідомі, Які Присутні у лінійній МОДЕЛІ, відповідно нефункціональнім обмеженності невід'ємні, что теж НЕ обмежує загальності підходу, бо є можлівість всегда перепозначіті
x j = - (x j ) - , де (x j ) - - від'ємне.
У залежності від вигляд функціональніх обмежень (нерівності або рівності) Загальну завдання лінійного програмування поділяють на:
а) канонічну, ЯКЩО k = 0; l = n, де УСІ функціональні обмеження мают вигляд рівностей;
б) стандартність (Симетричний), де k = m; l = n, де УСІ функціональні обмеження мают вигляд нерівностей.
Будь-які завдання лінійного програмування Можливо звесті до канонічної задачі Шляхом Перетворення функціональніх обмежень нерівностей у обмеження рівності доданням до нерівностей невідоміх невід'ємніх величин:
a i1 x 1 + A i2 x 2 + . . . + a in x n + y i = B i ;
де y i Ві 0; новим невідомім дають назви відповідно x n +1 ; x n +2 ; . . . ; х n + m ; та відповідно x j Ві 0, де j = 1 , 2,3 . . . n; n + 1 . . . n + m;
функціональні обмеження набуваються вигляд
n
S a ij x j <...
