інійне, цілочисельне, і стохастичне програмування). [Контровіч]. p> За широтою застосування різних методів у реальних процесах планування безсумнівним лідером є метод лінійної оптимізації , який був розроблений академіком Канторовичем в 30-ті роки ХХ-го століття. Найчастіше задача лінійного програмування застосовується при моделюванні організації виробництва. Ось як по Канторовичу виглядає математична модель організації виробництва:
У виробництві беруть участь M різних виробничих факторів (інгредієнтів) - робоча сила, сировина, матеріали, обладнання, кінцеві і проміжні продукти та ін Виробництво використовує S технологічних способів виробництва, причому для кожного з них задані обсяги вироблених інгредієнтів, розраховані на реалізацію цього способу з одиничною ефективністю, тобто заданий вектор a k = (a 1k , a 2k , ..., a mk ), k = 1,2 ..., S, в якому кожна з компонент a ik зазначає обсяг виробництва відповідного (i-го) інгредієнта, якщо вона позитивна; і обсяг його витрачання, якщо вона негативна (у способі k ). p> Вибір плану означає вказівка ​​інтенсивностей використання різних технологічних способів, тобто план визначається вектором x = (x 1 , x 2 , ..., x S ) c ненегативними компонентами [Контровіч].
Зазвичай на кількості випускаються і витрачаються інгредієнтів накладаються обмеження: провести потрібно не менше, ніж потрібно, а витрачатимуть не більше, ніж є. Такі обмеження записуються у вигляді
В
s
S a ik x k > b i ; I = 1,2, ..., m. p> k = 1
Якщо i> 0, то нерівність означає, що є потреба в інгредієнті у розмірі i, якщо i <0, то нерівність означає, що є ресурс даного інгредієнтів розмірі - I = | i |. Далі передбачається, що використання кожного способу, пов'язаного з витратою одного з перерахованих інгредієнтів або особливо виділеного інгредієнта в кількості Ck при одиничній інтенсивності способу k. В якості цільової функції приймається сумарна витрата цього інгредієнта в плані.
В
s
f (x) = S c k x k . p> k = 1
Тепер загальна задача лінійного програмування може бути представлена ​​в математичній формі. Для заданих чисел a ik , c k , і b i знайти
В
s
min S c k x k
k = 1
за умов
k> 0, k = 1,2, ..., s [1]
В В
s
S a ik x k > b i , i = 1,2, ..., m [2]
k = 1
План, що задовольняє умовам [1] і [2], є допустимим, а якщо в ньому, крім того, досягається мінімум цільової функції, то цей план оптимальний.
Задача лінійного програ...
