Линеарно програмирање (ЛП, или линеарна оптимизација) је математичка методологија за моделирање и решавање проблема налажења максимума или минимума линеарне функције, под условима исказаним као линеарне једначине или неједначине. Термин „програмирање“ је овде синоним за планирање, односно одређивање оптималног (најбољег) плана. То значи одређивање вредности променљивих таквих да дају оптималну вредност функције циља, при том задовољавајући услове (ограничења).

Линеарно програмирање је специјалан случај математичког програмирања (оптимизације), где су функција циља и ограничења линеарни.

Пример проблема линеарног програмирања са четири променљиве (скраћеница п.о. значи - при ограничењима):

Оваквим математичким моделима се могу представити проблеми алокације ресурса, планирања кретања возила, разни проблеми производње у индустрији, проблеми у економији итд. Применом линераног програмирања се могу решавати сви практични проблеми који могу да се искажу математичким моделом линеарног програмирања.

Историја Проблем линеарног програмирања је формулисао совјетски математичар Леонид Канторович 1939. године. Први модели су коришћени у дрвној производњи, a током Другог светског рата Канторович је радио за војску на оптимизацији војних операција. Метод решавања проблема није био јавно познат, све до 1947. када је Џорџ Б. Данциг објавио симплекс алгоритам.Dantzig, G.B.: . Објављен на у Koopmans T.C. (ed.):Activity Analysis of Production and Allocation, New York-London 1951 (Wiley & Chapman-Hall)

Решења проблема Скуп свих тачака у n-димензионалном простору које задовољавају ограничења проблема се назива допустивим скупом, или скупом допустивих решења. Тачка из овог скупа за коју је вредност функције циља оптимална (најбоља), односно максимална или минимална, се назива оптимално решење. Све тачке изван допустивог скупа су недопустива решења. Постоји више могућих случајева постојања решења у односу на то каква су ограничења: Проблем има јединствено оптимално решење Проблем има вишеструко оптимално решење (бесконачно много оптималних решења) Проблем нема оптимално решење (отворен је, раст функције циља није ограничен) Проблем уоште нема решење (ограничења су неконзистентна)

Облици проблема линеарног програмирања У општем случају проблем линеарног програмирања може бити исказан у облику чија су ограничења једначине или неједначине, са задатком максимизације или минимизације функције циља. Алгоритми који решавају ове проблеме (пре свега Симплекс) захтевају да проблем има одређен, специјалан облик, да би могао бити решаван. Постоје следећа четири облика проблема линеарног програмирања: општи симетрични стандардни канонски (условно, јер је ово у суштини интерни облик Симплекс алгоритма)

Општи облик Општи облик проблема линеарног програмирања подразумева задатак максимизације или минимизације функције циља при ограничењима исказаним као линеарне једначине или неједначине и додатним скупом природних ограничења да вредности променљивих не могу бити негативне.

Или исказан у сажетијем облику:

Симетрични облик Проблем исказан у симетричном облику има сва ограничења као неједнакости истог типа (сва имају знак или ). Такође, ако је задатак максимизација функције циља, ограничења морају да буду типа , а ако је задатак минимизација, ограничења морају да буду типа .

Овде је дат симетрични облик у матричној форми, где су коефицијенти функције циља, скуп променљивих и слободни чланови ограничења дати као вектори, а коефицијенти неједначина ограничења су дати као матрица.

+ Симетрични облик у матричној форми Варјанта максимизације Варјанта минимизације Значење ознака

Стандардни облик Проблем исказан у стандардном облику може да буде проблем максимизације или минимизације, а сва ограничења морају да буду једнакости. Осим овог услова скуп ограничења мора да задовољи још неке услове: Једначине ограничења треба да буду линеарно независне Ако нису, то значи да две или више једначина из скупа исказују исто ограничење, и дупликати се могу елиминисати из проблема. Број ограничења треба да буде мањи од броја променљивих Ако је испуњен први услов, а број променљивих и једначина је исти, тада проблем има само једно допустиво решење, односно допустива област ће се састојати од само једне тачке. А ако је, уз испуњење првог услова, број једначина већи од броја променљивих, онда проблем неће имати решења, односно биће преограничен. Сви слободни чланови једначина ограничења треба да буду ненегативни Ови додатни услови се могу сажети у следећем (n - број променљивих, m - број ограничења):

Стандардни облик у матричној форми

Превођење из општег у симетрични и стандардни облик Модели практичних проблема су изворно најчешће у симетричном облику или у општем, али са само једним типом неједнакости (и са једнакостима, наравно). Практични проблеми скоро никад нису изворно у стандардном облику. Модели у једном облику се могу преводити у еквивалентне моделе у неком другом облику. За превођење се могу користити више различитих техника, чијим коришћењем се било који модел у општем, симетричном или стандардном облику, може превести у неки од друга два.

Промена задатка проблема (макс. или мин.)

У случају да нам више одговара супротан проблем од датог (макс. у односу на мин. и обратно), све што треба да се уради је да се функција циља помножи са -1, односно да се вектор коефицијената помножи са -1.

Промена типа неједнакости

Модел у општем облику чија су сва ограничења неједнакости, се може превести у симетрични облик тако што се сва ограничења која не одговарају задатку (макс. или мин.) множе са -1, чиме се обрће знак неједнакости.

Превођење неједначина у једначине

Ако је потребано да проблем буде у стандардном облику, све неједначине из скупа ограничења морају се превести у еквивалентне једначине. Ово се постиже тако што се у проблем убацују нове променљиве, које се зову изравњавајуће, и то по једна у сваку неједначину. У неједначине типа „мање-једнако“ додаје се изравњавајућа променљива са коефицијентом 1.

У неједначине типа „веће-једнако“ додаје се изравњавајућа променљива са коефицијентом -1.

Изравњавајуће променљиве се не додају у функцију циља, односно може се сматрати да у функцији циља имају коефицијенте 0. После превођења проблем ће имати онолико додатних променљивих колико је било неједначина у скупу ограничења. Резултујући проблем у стандардном облику је еквивалентан почетном проблему у смислу да ће се његовим решавањем добити оптимално решење почетног проблема, при том се у решењу вредности додатних изравњавајућих променљивих могу игнорисати.

Превођење једначина у неједначине

Једначине се могу превести у неједначине на више начина: Операција обрнута додавању изравњавајуће променљиве Из једначине се може елиминисати променљива које нема у функцији циља, а ни у осталим ограничењима, чији коефицијент у једначини је позитиван и која је ограничена да буде ненегативна. Тада једначина прелази у неједначину типа ”мање-једнако”. Ако је променљива има негативан коефицијент, онда се добија једначина ”веће-једнако”. У случају да је променљива ограничена да буде непозитивна, онда се правила за знак коефицијента окрећу.

Замена једне једначине са две неједначине Ове две нејадначине ће имати исте коефицијенте и слободне чланове као почетна једначина, али са обрнутим знаковима неједнакости. Пошто знакови неједнакости укључују и могућност једнакости (”мање-једнако” и ”веће-једнако”), а супротни су, то значи да се те две неједначине могу свести на једну једначину.

Елиминисање променљивих неограничених по знаку

Проблем може да буде формулисан тако да неке променљиве нису ограничене по знаку (могу бити и позитивне и негативне). У овом случају може се направити смена. Неку променљиву можемо заменити разликом две променљиве на свим местима у проблему где се појављује. Сада ове две нове променљиве могу да буду ограничене да буду ненегативне, јер њихова разлика може да буде и позитивна и негативна, као оригинална променљива.

Канонски облик Канонски облик проблема линеарног програмирања је скоро специјалан случај стандардног облика (скоро, јер има једно проширење у односу на општи облик проблема ЛП). Овај облик је заправо интерни облик проблема Симплекс алгоритма. Проблем у канонском облику осим што задовољава услове стандардног облика, такође има и следеће додатне услове. Ако проблем има променљивих и ограничења, он је у канонском ако задовољава следеће услове: Задатак проблема је максимизација функције циља. У скупу променљивих постоји подскуп од m променљивих, таквих да се у сваком ограничењу налази по једна променљива из тог подскупа (и ни у једном другом ограничењу), и то са коефицијентом 1. Тих m променљивих из подскупа у функцији циља имају коефицијент 0. Сви слободни чланови ограничења су ненегативни.

Такође има и једно проширење у односу на општи облик, а то је да функција циља може да садржи слободан члан.

Развијено Матрично

Базне променљиве и базна допустива решења

Ако имамо проблем у стандардном облику, са матрицом ограничења , од свих променљивих можемо да изаберемо неких m променљивих, таквих да, ако остале променљиве изједначимо са нулом систем једначина ограничења може да се јединствено реши по изабраних m променљивих. Познато је да, да би систем једначина био решив, матрица коефицијената променљивих мора да буде инвертибилна, односно да има детерминанту различиту од 0. Ових m променљивих које задовољавају услов се називају базне променљиве, скуп базних променљивих се назива база, а квадратна матрица коефицијената базних променљивих се назива матрица базе.

Решавањем система једначина добијеног на овај начин добијају се вредности базних променљивих. Тако добијене вредности базних променљивих са додатим нулама као вредностима осталих (небазних) променљивих чине једно допустиво решење проблема, јер оно сигурно задовољава ограничења. Овако добијено допустиво решење се назива базно допустиво решење. Проблем има онолико базних допустивих решења, колико матрица коефицијената ограничења има квадратних инвертибилних подматрица величине m.

Ако вектор коефицијената базних променљивих у функцији циља означимо са , тада ће вредност функције циља за дато базно допустиво решење бити једнака , односно .

Ако проблем има јединствено оптимално решење, тада ће једно од базних допустивих решења бити то оптимално решење, а ако систем има бесконачно много оптималних решења, тада ће више од једног базног допустивог решења имати оптималну вредност функције циља. Ако се открију све инвертибилне подматрице величине m, и преко њих генеришу сва базна допустива решења, она решења која дају најбољу вредност функције циља јесу оптимална решења проблема. Наравно, овај начин решавања проблема линеарног програмирања је јако неефикасан, јер подразумева пробање свих могућности.

Базна допустива решења у канонском облику

Ако имамо проблем у канонском облику можемо директно прочитати једно базно допустиво решење, без решавања систем једначина. Матрица коефицијената већ има јасно видљиву инвертибилну подматрицу (јединичну матрицу за m променљивих) и ако небазним променљивама доделимо вредност 0, одмах видимо да су решења система једначина заправо слободни чланови једначина.

Свођење стандардног облика на канонски

Методе линеарне алгебре

Ако имамо проблем у стандардном облику, и позната нам је једна база, тада можемо проблем да сведемо на канонски облик у односу на ту базу, али под условом да слободни чланови ограничења резултујућег канонског облика буду ненегативни.

Превођење ограничења

Ако променљиве у ограничењима групишемо у базне и небазне, можемо методама линеарне алгебре (инверзија матрице или Гаус-Жорданова редукција) да трансформишемо систем једначина тако да матрица базе постане јединична матрица (што захтева канонски облик). Матрица небазних променљивих тада постаје матрица , док вектор постаје .