Лінійне програмування або лінійна оптимізація (LP, англ. Linear Programming) — метод досягнення найліпшого виходу (такого як найбільший прибуток або найменша вартість) у математичній моделі, чиї вимоги подані через лінійні відношення. Лінійне програмування є особливим випадком математичного програмування (математичної оптимізації).
Формальніше, лінійне програмування є технікою для оптимізації лінійної цільової функції, що обмежена лінійними рівняннями і лінійними нерівностями. Її допустима множина є опуклим політопом, який є множиною визначеною як перетин скінченної кількості півпростірів, кожен з яких визначає лінійна нерівність. Її цільова функція є дійсно-значима афінна функція визначена на цьому багатограннику. Алгоритм лінійного програмування знаходить точку на багатограннику, де ця функція набуває найбільшого чи найменшого значення, якщо така точка існує.
Загальні відомості
Лінійне програмування (та дослідження задачі лінійного програмування) є однією із найрозвинутишіх галузей математичного програмування та теорії оптимізації. Загальна постановка задачі лінійного програмування, та один із підходів до її розв'язання (ідея розрішаючих множників або двоїстих оцінок) вперше наведено в роботі радянського вченого Канторовича Л. В. в 1939. В цій же роботі намічено один із методів розв'язання задачі — метод послідовного зменшення нев'язок.
Задача лінійного програмування
Зада́ча ліні́йного програмува́ння — задача оптимізації з лінійною цільовою функцією та допустимою множиною обмеженою лінійними рівностями або нерівностями.
Її можна виразити в канонічній формі:
максимізувати за умов і також
де x представляє вектор змінних (треба визначити), c і b це вектори (відомих) коефіцієнтів, A це (відома) матриця коефіцієнтів і це транспонована матриця. Вираз, який необхідно максимізувати або мінімізувати називають цільова функція (тут cTx). Нерівності Ax ≤ b і x ≥ 0 є обмеженнями, які визначають опуклий політоп над яким оптимізують цільову функцію.
Тобто, необхідно мінімізувати
- (1)
при обмеженнях
- , (2)
- , (3)
- , (4)
де cj (j = 1, …, n), aij(i = 1, …, m) — задані числа.
Задача максимізації функції (1) зводиться до задачі мінімізації шляхом заміни знаків всіх коефіцієнтів cj на протилежні.
Методи розв'язання
- — розроблений в 1940 радянськими вченими Канторовичем та в застосуванні до транспортної задачі;
- Симплекс-метод — цей метод є узагальненням методу потенціалів для випадку загальної задачі лінійного програмування. Розроблений американським вченим Данциґом Дж.-Б. в 1949 році.
- розроблений згодом після прямого симплекс-методу, і який є, за сутністю, симплекс-методом розв'язання двоїстої задачі лінійного програмування, але сформульованої в термінах вихідної задачі.
Усі ці методи скінченні. Крім того, існують, також, ітеративні методи розв'язання, які дають можливість обчислювати розв'язки задачі із наперед заданою точністю.
Близький зв'язок між лінійним програмуванням та теорією ігор дає змогу використовувати для розв'язання задач лінійного програмування чисельні методи теорії ігор.
Інша група ітеративних методів характеризується заміною вихідної задачі на еквівалентну їй задачу опуклої оптимізації без обмежень, для розв'язання якої використовуються різноманітні градієнтні методи.
Для розв'язання задач лінійного програмування з великою кількістю змінних та обмежень використовують методи декомпозиції, які дають змогу замість вихідної задачі розв'язувати послідовність задач меншого обсягу.
Методів лінійного програмування недостатньо при накладанні додаткового обмеження цілочисельністі значень змінних. Вивченням таких задач займається цілочисельне програмування.
Поряд з основною задачею лінійного програмування, розглядають різноманітні окремі задачі лінійного програмування, такі як транспортні, задачі розподілу, задачі теорії розкладів, вибору тощо.
Двоїсті задачі лінійного програмування
Кожній задачі лінійного програмування вигляду
можна певним чином зіставити деяку іншу задачу лінійного програмування, звану двоїстою або спряженою відносно початкової або прямої. Зв'язок вихідної початкової та двоїстої задач полягає головним чином у тому, що розв'язок однієї з них можна легко отримати безпосередньо з розв'язку іншої. Дамо визначення двоїстої задачі відносно до початкової задачі лінійного програмування
Початкова задача | Двоїста задача |
---|---|
Якщо вектори і — допустимі розв'язки прямої та двоїстої задач, то , причому рівність досягається тоді й лише тоді, коли і — оптимальні розв'язки. Якщо ж цільова функція однієї з пари двоїстих задач не обмежена (для початкової — зверху, для двоїстої — знизу), то область допустимих розв'язків іншої задачі — порожня.
Якщо вектори і — оптимальні розв'язки прямої та двоїстої задачі, відповідно, то виконуються такі рівності
Тобто, для оптимальних розв'язків прямої та двоїстої задач, ненапруженим (виконується строга нерівність) обмеженням відповідають нульові змінні, а ненульовим змінним (що входять в опорний план) відповідають напружені (нестрога нерівність реалізується, як рівність) обмеження. Але можуть бути й нульові змінні, що відповідають напруженим обмеженням.
Ці властивості двоїстих розв'язків дозволяють істотно скоротити час розв'язування, якщо доводиться розв'язувати задачу з кількістю обмежень значно більшою від кількості змінних. Тоді можна, розв'язавши двоїсту задачу, знайти її опорний план, після чого, відібравши у прямій задачі лише обмеження, що відповідають опорному плану (всі ці обмеження мають бути напруженими), розв'язати для них звичайну систему лінійних рівнянь.
Використання
Лінійне програмування можна застосувати у різноманітних галузях науки. Його використовують в економіці і бізнесі, але можна використати і в інженерних задачах. Серед галузей які використовують лінійне програмування можна згадати перевезення, енергетику, телекомунікації і виробництво. Воно довело свою корисність у моделюванні різних типів проблем у плануванні, маршрутизації, призначенні задач і дизайні.
Див. також
Примітки
- Электронный учебник «Экономико-математические методы». Двойственность в линейном программировании [ 17 червня 2016 у Wayback Machine.]
Джерела інформації
- Енциклопедія кібернетики, , т. 2, с. 232-234.
Література
- Цегелик Г.Г. Лінійне програмування. – Львів: Світ, 1995. – 215 с. –
Посилання
- Linear Program Solver (LiPS) [ 6 червня 2011 у Wayback Machine.] — розв'язувач задач лінійного цілочисельного программирования.
- Двоїстість у лінійному програмуванні - тлумачення [ 28 січня 2020 у Wayback Machine.].
- Динамічні математичні моделі[недоступне посилання з липня 2019]
Це незавершена стаття з математики. Ви можете проєкту, виправивши або дописавши її. |
Ця стаття потребує додаткових для поліпшення її . (грудень 2018) |
В іншому мовному розділі є повніша стаття Linear programming(англ.). Ви можете допомогти, розширивши поточну статтю за допомогою з англійської.
|
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Linijne programuvannya abo linijna optimizaciya LP angl Linear Programming metod dosyagnennya najlipshogo vihodu takogo yak najbilshij pributok abo najmensha vartist u matematichnij modeli chiyi vimogi podani cherez linijni vidnoshennya Linijne programuvannya ye osoblivim vipadkom matematichnogo programuvannya matematichnoyi optimizaciyi Grafichne predstavlennya prostoyi linijnoyi programi z dvoma zminnimi i shistma nerivnostyami Mnozhina dopustimih rozv yazkiv zobrazhena svitlo zhovtim i utvoryuye bagatogrannik 2 vimirnij politop Cilova funkciya predstavlena chervonoyu liniyeyu i strilkoyu Chervona liniya ce mnozhina rivnya cilovoyi funkciyi i strilka poznachaye v yakomu napryamku mi optimizuyemo Formalnishe linijne programuvannya ye tehnikoyu dlya optimizaciyi linijnoyi cilovoyi funkciyi sho obmezhena linijnimi rivnyannyami i linijnimi nerivnostyami Yiyi dopustima mnozhina ye opuklim politopom yakij ye mnozhinoyu viznachenoyu yak peretin skinchennoyi kilkosti pivprostiriv kozhen z yakih viznachaye linijna nerivnist Yiyi cilova funkciya ye dijsno znachima afinna funkciya viznachena na comu bagatogranniku Algoritm linijnogo programuvannya znahodit tochku na bagatogranniku de cya funkciya nabuvaye najbilshogo chi najmenshogo znachennya yaksho taka tochka isnuye Zagalni vidomostiLinijne programuvannya ta doslidzhennya zadachi linijnogo programuvannya ye odniyeyu iz najrozvinutishih galuzej matematichnogo programuvannya ta teoriyi optimizaciyi Zagalna postanovka zadachi linijnogo programuvannya ta odin iz pidhodiv do yiyi rozv yazannya ideya rozrishayuchih mnozhnikiv abo dvoyistih ocinok vpershe navedeno v roboti radyanskogo vchenogo Kantorovicha L V v 1939 V cij zhe roboti namicheno odin iz metodiv rozv yazannya zadachi metod poslidovnogo zmenshennya nev yazok Zadacha linijnogo programuvannyaZada cha lini jnogo programuva nnya zadacha optimizaciyi z linijnoyu cilovoyu funkciyeyu ta dopustimoyu mnozhinoyu obmezhenoyu linijnimi rivnostyami abo nerivnostyami Yiyi mozhna viraziti v kanonichnij formi maksimizuvati c T x displaystyle mathbf c mathrm T mathbf x za umov A x b displaystyle A mathbf x leq mathbf b i takozh x 0 displaystyle mathbf x geq mathbf 0 de x predstavlyaye vektor zminnih treba viznachiti c i b ce vektori vidomih koeficiyentiv A ce vidoma matricya koeficiyentiv i T displaystyle cdot mathrm T ce transponovana matricya Viraz yakij neobhidno maksimizuvati abo minimizuvati nazivayut cilova funkciya tut cTx Nerivnosti Ax b i x 0 ye obmezhennyami yaki viznachayut opuklij politop nad yakim optimizuyut cilovu funkciyu Tobto neobhidno minimizuvati j 1 n c j x j min displaystyle sum j 1 n c j x j to min 1 pri obmezhennyah j 1 n a i j x j b i i 1 m 1 displaystyle sum j 1 n a ij x j leq b i i 1 dots m 1 2 j 1 n a i j x j b i i m 1 1 m displaystyle sum j 1 n a ij x j b i i m 1 1 dots m 3 x j 0 j 1 n 1 displaystyle x j geq 0 j 1 dots n 1 4 de cj j 1 n aij i 1 m zadani chisla Zadacha maksimizaciyi funkciyi 1 zvoditsya do zadachi minimizaciyi shlyahom zamini znakiv vsih koeficiyentiv cj na protilezhni Metodi rozv yazannya rozroblenij v 1940 radyanskimi vchenimi Kantorovichem ta v zastosuvanni do transportnoyi zadachi Simpleks metod cej metod ye uzagalnennyam metodu potencialiv dlya vipadku zagalnoyi zadachi linijnogo programuvannya Rozroblenij amerikanskim vchenim Dancigom Dzh B v 1949 roci rozroblenij zgodom pislya pryamogo simpleks metodu i yakij ye za sutnistyu simpleks metodom rozv yazannya dvoyistoyi zadachi linijnogo programuvannya ale sformulovanoyi v terminah vihidnoyi zadachi Usi ci metodi skinchenni Krim togo isnuyut takozh iterativni metodi rozv yazannya yaki dayut mozhlivist obchislyuvati rozv yazki zadachi iz napered zadanoyu tochnistyu Blizkij zv yazok mizh linijnim programuvannyam ta teoriyeyu igor daye zmogu vikoristovuvati dlya rozv yazannya zadach linijnogo programuvannya chiselni metodi teoriyi igor Insha grupa iterativnih metodiv harakterizuyetsya zaminoyu vihidnoyi zadachi na ekvivalentnu yij zadachu opukloyi optimizaciyi bez obmezhen dlya rozv yazannya yakoyi vikoristovuyutsya riznomanitni gradiyentni metodi Dlya rozv yazannya zadach linijnogo programuvannya z velikoyu kilkistyu zminnih ta obmezhen vikoristovuyut metodi dekompoziciyi yaki dayut zmogu zamist vihidnoyi zadachi rozv yazuvati poslidovnist zadach menshogo obsyagu Metodiv linijnogo programuvannya nedostatno pri nakladanni dodatkovogo obmezhennya cilochiselnisti znachen zminnih Vivchennyam takih zadach zajmayetsya cilochiselne programuvannya Poryad z osnovnoyu zadacheyu linijnogo programuvannya rozglyadayut riznomanitni okremi zadachi linijnogo programuvannya taki yak transportni zadachi rozpodilu zadachi teoriyi rozkladiv viboru tosho Dvoyisti zadachi linijnogo programuvannyaDiv takozh Dvoyistist optimizaciya Kozhnij zadachi linijnogo programuvannya viglyadu j 1 n a i j x j c i i 1 m displaystyle sum j 1 n a ij x j leqslant c i i overline 1 m x j 0 j 1 n displaystyle x j geqslant 0 j overline 1 n F x j 1 n b j x j max displaystyle F x sum j 1 n b j x j to max mozhna pevnim chinom zistaviti deyaku inshu zadachu linijnogo programuvannya zvanu dvoyistoyu abo spryazhenoyu vidnosno pochatkovoyi abo pryamoyi Zv yazok vihidnoyi pochatkovoyi ta dvoyistoyi zadach polyagaye golovnim chinom u tomu sho rozv yazok odniyeyi z nih mozhna legko otrimati bezposeredno z rozv yazku inshoyi Damo viznachennya dvoyistoyi zadachi vidnosno do pochatkovoyi zadachi linijnogo programuvannya Pochatkova zadacha Dvoyista zadacha j 1 n a i j x j c i i 1 m displaystyle sum j 1 n a ij x j leqslant c i i overline 1 m y i 0 i 1 m displaystyle y i geqslant 0 i overline 1 m x j 0 j 1 n displaystyle x j geqslant 0 j overline 1 n i 1 m a i j y i b j j 1 n displaystyle sum i 1 m a ij y i geqslant b j j overline 1 n F x j 1 n b j x j max displaystyle F x sum j 1 n b j x j to max T y i 1 m c i y i min displaystyle T y sum i 1 m c i y i to min Yaksho vektori x displaystyle x i y displaystyle y dopustimi rozv yazki pryamoyi ta dvoyistoyi zadach to F x T y displaystyle F x leqslant T y prichomu rivnist dosyagayetsya todi j lishe todi koli x displaystyle x i y displaystyle y optimalni rozv yazki Yaksho zh cilova funkciya odniyeyi z pari dvoyistih zadach ne obmezhena dlya pochatkovoyi zverhu dlya dvoyistoyi znizu to oblast dopustimih rozv yazkiv inshoyi zadachi porozhnya Yaksho vektori x displaystyle x i y displaystyle y optimalni rozv yazki pryamoyi ta dvoyistoyi zadachi vidpovidno to vikonuyutsya taki rivnosti x j i 1 m a i j y i b j 0 j 1 n displaystyle x j sum i 1 m a ij y i b j 0 j overline 1 n y i j 1 n a i j x j c i 0 i 1 m displaystyle y i sum j 1 n a ij x j c i 0 i overline 1 m Tobto dlya optimalnih rozv yazkiv pryamoyi ta dvoyistoyi zadach nenapruzhenim vikonuyetsya stroga nerivnist obmezhennyam vidpovidayut nulovi zminni a nenulovim zminnim sho vhodyat v opornij plan vidpovidayut napruzheni nestroga nerivnist realizuyetsya yak rivnist obmezhennya Ale mozhut buti j nulovi zminni sho vidpovidayut napruzhenim obmezhennyam Ci vlastivosti dvoyistih rozv yazkiv dozvolyayut istotno skorotiti chas rozv yazuvannya yaksho dovoditsya rozv yazuvati zadachu z kilkistyu obmezhen znachno bilshoyu vid kilkosti zminnih Todi mozhna rozv yazavshi dvoyistu zadachu znajti yiyi opornij plan pislya chogo vidibravshi u pryamij zadachi lishe obmezhennya sho vidpovidayut opornomu planu vsi ci obmezhennya mayut buti napruzhenimi rozv yazati dlya nih zvichajnu sistemu linijnih rivnyan VikoristannyaLinijne programuvannya mozhna zastosuvati u riznomanitnih galuzyah nauki Jogo vikoristovuyut v ekonomici i biznesi ale mozhna vikoristati i v inzhenernih zadachah Sered galuzej yaki vikoristovuyut linijne programuvannya mozhna zgadati perevezennya energetiku telekomunikaciyi i virobnictvo Vono dovelo svoyu korisnist u modelyuvanni riznih tipiv problem u planuvanni marshrutizaciyi priznachenni zadach i dizajni Div takozhPortal Matematika Cilochislovi zadachi linijnogo programuvannya Zadacha matematichnogo programuvannya Zadacha optimizaciyi Opornij plan Model vitrati vipusk Geometrichne programuvannyaPrimitkiElektronnyj uchebnik Ekonomiko matematicheskie metody Dvojstvennost v linejnom programmirovanii 17 chervnya 2016 u Wayback Machine Dzherela informaciyiEnciklopediya kibernetiki t 2 s 232 234 LiteraturaCegelik G G Linijne programuvannya Lviv Svit 1995 215 s ISBN 5 7773 0217 3PosilannyaLinear Program Solver LiPS 6 chervnya 2011 u Wayback Machine rozv yazuvach zadach linijnogo cilochiselnogo programmirovaniya Dvoyistist u linijnomu programuvanni tlumachennya 28 sichnya 2020 u Wayback Machine Dinamichni matematichni modeli nedostupne posilannya z lipnya 2019 Ce nezavershena stattya z matematiki Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi Cya stattya potrebuye dodatkovih posilan na dzherela dlya polipshennya yiyi perevirnosti Bud laska dopomozhit udoskonaliti cyu stattyu dodavshi posilannya na nadijni avtoritetni dzherela Zvernitsya na storinku obgovorennya za poyasnennyami ta dopomozhit vipraviti nedoliki Material bez dzherel mozhe buti piddano sumnivu ta vilucheno gruden 2018 V inshomu movnomu rozdili ye povnisha stattya Linear programming angl Vi mozhete dopomogti rozshirivshi potochnu stattyu za dopomogoyu perekladu z anglijskoyi Divitis avtoperekladenu versiyu statti z movi anglijska Perekladach povinen rozumiti sho vidpovidalnist za kincevij vmist statti u Vikipediyi nese same avtor redaguvan Onlajn pereklad nadayetsya lishe yak korisnij instrument pereglyadu vmistu zrozumiloyu movoyu Ne vikoristovujte nevichitanij i nevidkorigovanij mashinnij pereklad u stattyah ukrayinskoyi Vikipediyi Mashinnij pereklad Google ye korisnoyu vidpravnoyu tochkoyu dlya perekladu ale perekladacham neobhidno vipravlyati pomilki ta pidtverdzhuvati tochnist perekladu a ne prosto skopiyuvati mashinnij pereklad do ukrayinskoyi Vikipediyi Ne perekladajte tekst yakij vidayetsya nedostovirnim abo neyakisnim Yaksho mozhlivo perevirte tekst za posilannyami podanimi v inshomovnij statti Dokladni rekomendaciyi div Vikipediya Pereklad