Линеарно програмирање

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

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

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

${\begin{aligned}&{\text{max}}&&f(\mathbf {x} )=x_{1}+3x_{2}+5x_{3}+2x_{4}\\&{\text{p.o.}}&&2x_{1}+3x_{3}\leq 234\\&&&5x_{2}+4x_{4}\leq 180\\&&&x_{1}+x_{2}+x_{2}\leq 300\\&&&x_{1}\geq 0,\ x_{2}\geq 0,\ x_{3}\geq 0\ x_{4}\geq 0\end{aligned}}$

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

Историја

Проблем линеарног програмирања је формулисао совјетски математичар Леонид Канторович 1939. године. Први модели су коришћени у дрвној производњи, a током Другог светског рата Канторович је радио за војску на оптимизацији војних операција. Метод решавања проблема није био јавно познат, све до 1947. када је Џорџ Б. Данциг објавио симплекс алгоритам.

Решења проблема

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

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

Облици проблема линеарног програмирања

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

• општи
• симетрични
• стандардни
• канонски (условно, јер је ово у суштини интерни облик Симплекс алгоритма)

Општи облик

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

${\begin{aligned}&{\text{min}}\mid {\text{max}}&&f(\mathbf {x} )=c_{1}x_{1}+c_{2}x_{2}+...+c_{n}x_{n}\\&{\text{p.o.}}&&a_{11}x_{1}+a_{12}x_{2}+...+a_{1n}x_{n}\lesseqqgtr b_{1}\\&&&a_{21}x_{1}+a_{22}x_{2}+...+a_{2n}x_{n}\lesseqqgtr b_{2}\\&&&\vdots \\&&&a_{m1}x_{1}+a_{m2}x_{2}+...+a_{mn}x_{n}\lesseqqgtr b_{m}\\&&&x_{1}\geq 0,\ x_{2}\geq 0,\ ...,\ x_{n}\geq 0\end{aligned}}$

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

${\begin{aligned}&{\text{min}}\mid {\text{max}}&&f(\mathbf {x} )=\sum _{i=1}^{n}c_{i}x_{i}\\&{\text{p.o.}}&&\sum _{j=1}^{n}a_{ij}x_{j}\lesseqqgtr b_{i},\ i=1,2,...,m\\&&&x_{j}\geq 0,\ j=1,2,...,n\end{aligned}}$

Симетрични облик

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

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

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

Варјанта максимизације	Варјанта минимизације	Значење ознака
${\begin{aligned}&{\text{max}}&&f(\mathbf {x} )=\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{p.o.}}&&A\mathbf {x} \leq \mathbf {b} \\&&&\mathbf {x} \geq \mathbf {0} \end{aligned}}$	${\begin{aligned}&{\text{min}}&&f(\mathbf {x} )=\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{p.o.}}&&A\mathbf {x} \geq \mathbf {b} \\&&&\mathbf {x} \geq \mathbf {0} \end{aligned}}$	$\mathbf {x} ={\begin{bmatrix}x_{1}\\\vdots \\x_{n}\end{bmatrix}},\mathbf {c} ={\begin{bmatrix}c_{1}\\\vdots \\c_{n}\end{bmatrix}},\mathbf {b} ={\begin{bmatrix}b_{1}\\\vdots \\b_{m}\end{bmatrix}},A={\begin{bmatrix}a_{11}&\cdots &a_{1n}\\\vdots &\ddots &\vdots \\a_{m1}&\cdots &a_{mn}\end{bmatrix}}$

Стандардни облик

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

• Једначине ограничења треба да буду линеарно независне

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

• Број ограничења треба да буде мањи од броја променљивих

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

• Сви слободни чланови једначина ограничења треба да буду ненегативни

Ови додатни услови се могу сажети у следећем (n - број променљивих, m - број ограничења):

$\mathrm {rang} A=m<n$

$\mathbf {b} \geq \mathbf {0}$

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

${\begin{aligned}&{\text{min}}\mid {\text{max}}&&f(\mathbf {x} )=\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{p.o.}}&&A\mathbf {x} =\mathbf {b} \\&&&\mathbf {x} \geq \mathbf {0} \end{aligned}}$

Превођење из општег у симетрични и стандардни облик

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

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

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

${\text{max}}\ \ f(\mathbf {x} )=\mathbf {c} ^{\mathrm {T} }\mathbf {x} \ \ \rightarrow \ \ {\text{min}}\ \ f(\mathbf {x} )=(-\mathbf {c} )^{\mathrm {T} }\mathbf {x}$

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

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

${\begin{aligned}&{\text{max}}&&f(\mathbf {x} )=\mathbf {c} ^{\mathrm {T} }\mathbf {x} &&&&{\text{max}}&&f(\mathbf {x} )=\mathbf {c} ^{\mathrm {T} }\mathbf {x} &&&&{\text{max}}&&f(\mathbf {x} )=\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{p.o.}}&&{\begin{matrix}A_{l}\mathbf {x} \leq \mathbf {b} _{l}\\A_{g}\mathbf {x} \geq \mathbf {b} _{g}\end{matrix}}&&\rightarrow &&{\text{p.o.}}&&{\begin{matrix}A_{l}\mathbf {x} \leq \mathbf {b} _{l}\\-A_{g}\mathbf {x} \leq -\mathbf {b} _{g}\end{matrix}}&&\rightarrow &&{\text{p.o.}}&&{\begin{bmatrix}A_{l}\\-A_{g}\end{bmatrix}}\mathbf {x} \leq {\begin{bmatrix}\mathbf {b} _{l}\\-\mathbf {b} _{g}\end{bmatrix}}\\&&&\mathbf {x} \geq \mathbf {0} &&&&&&\mathbf {x} \geq \mathbf {0} &&&&&&\mathbf {x} \geq \mathbf {0} \\\end{aligned}}$

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

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

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

$a_{j1}x_{1}+a_{j2}+...+a_{jn}x_{n}\leq b_{j}\ \ \rightarrow \ \ a_{j1}x_{1}+a_{j2}+...+a_{jn}x_{n}+s_{j}=b_{j}$

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

$a_{j1}x_{1}+a_{j2}+...+a_{jn}x_{n}\geq b_{j}\ \ \rightarrow \ \ a_{j1}x_{1}+a_{j2}+...+a_{jn}x_{n}-s_{j}=b_{j}$

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

${\begin{aligned}&{\text{max}}&&f(\mathbf {x} )=\mathbf {c} ^{\mathrm {T} }\mathbf {x} &&&&{\text{max}}&&f(\mathbf {x} )=\mathbf {c} ^{\mathrm {T} }\mathbf {x} &&&&{\text{max}}&&f(\mathbf {x} )=\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{p.o.}}&&{\begin{matrix}A_{l}\mathbf {x} \leq \mathbf {b} _{l}\\A_{g}\mathbf {x} \geq \mathbf {b} _{g}\\A_{e}\mathbf {x} =\mathbf {b} _{e}\end{matrix}}&&\rightarrow &&{\text{p.o.}}&&{\begin{matrix}A_{l}\mathbf {x} +\mathbf {s} _{l}=\mathbf {b} _{l}\\A_{g}\mathbf {x} -\mathbf {s} _{g}=\mathbf {b} _{g}\\A_{e}\mathbf {x} =\mathbf {b} _{e}\end{matrix}}&&\rightarrow &&{\text{p.o.}}&&{\begin{bmatrix}A_{l}&I&0\\A_{g}&0&-I\\A_{e}&0&0\end{bmatrix}}{\begin{bmatrix}\mathbf {x} \\\mathbf {s} _{l}\\\mathbf {s} _{g}\end{bmatrix}}={\begin{bmatrix}\mathbf {b} _{l}\\\mathbf {b} _{g}\\\mathbf {b} _{e}\end{bmatrix}}\\&&&\mathbf {x} \geq \mathbf {0} &&&&&&\mathbf {x} \geq \mathbf {0} &&&&&&\mathbf {x} \geq \mathbf {0} \\&&&&&&&&&\mathbf {s} \geq \mathbf {0} &&&&&&\mathbf {s} \geq \mathbf {0} \\\end{aligned}}$

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

Једначине се могу превести у неједначине на више начина:

• Операција обрнута додавању изравњавајуће променљиве

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

${\begin{aligned}&a_{i1}x_{1}+a_{i2}x_{2}+a_{i3}x_{3}+a_{is1}s_{1}=b_{i},(s_{1}\geq 0)&&\rightarrow &&a_{i1}x_{1}+a_{i2}x_{2}+a_{i3}x_{3}\leq b_{i}\\&a_{i1}x_{1}+a_{i2}x_{2}+a_{i3}x_{3}-a_{is1}s_{1}=b_{i},(s_{1}\geq 0)&&\rightarrow &&a_{i1}x_{1}+a_{i2}x_{2}+a_{i3}x_{3}\geq b_{i}\\&a_{i1}x_{1}+a_{i2}x_{2}+a_{i3}x_{3}+a_{is1}s_{1}=b_{i},(s_{1}\leq 0)&&\rightarrow &&a_{i1}x_{1}+a_{i2}x_{2}+a_{i3}x_{3}\geq b_{i}\\&a_{i1}x_{1}+a_{i2}x_{2}+a_{i3}x_{3}-a_{is1}s_{1}=b_{i},(s_{1}\leq 0)&&\rightarrow &&a_{i1}x_{1}+a_{i2}x_{2}+a_{i3}x_{3}\leq b_{i}\\\end{aligned}}$

• Замена једне једначине са две неједначине

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

${\begin{aligned}&a_{i1}x_{1}+a_{i2}x_{2}+a_{i3}x_{3}=b_{i}&&\rightarrow &&a_{i1}x_{1}+a_{i2}x_{2}+a_{i3}x_{3}\leq b_{i}\\&&&&&a_{i1}x_{1}+a_{i2}x_{2}+a_{i3}x_{3}\geq b_{i}\\\end{aligned}}$

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

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

Канонски облик

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

• Задатак проблема је максимизација функције циља.
• У скупу променљивих постоји подскуп од m променљивих, таквих да се у сваком ограничењу налази по једна променљива из тог подскупа (и ни у једном другом ограничењу), и то са коефицијеном 1.
• Тих m променљивих из подскупа у функцији циља имају коефицијент 0.
• Сви слободни чланови ограничења су ненегативни.

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

Развијено	Матрично
${\begin{aligned}&{\text{max}}&&f(\mathbf {x} )=c_{1}x_{1}+...+c_{n-m}x_{n-m}+F_{0}\\&{\text{p.o.}}&&a_{11}x_{1}+a_{12}x_{2}+...+a_{1(n-m)}x_{n-m}+x_{n-m+1}=b_{1}\\&&&a_{21}x_{1}+a_{22}x_{2}+...+a_{2(n-m)}x_{n-m}+x_{n-m+2}=b_{2}\\&&&\vdots \\&&&a_{m1}x_{1}+a_{m2}x_{2}+...+a_{m(n-m)}x_{n-m}+x_{n}=b_{m}\\&&&x_{i}\geq 0,\ i=1,...,n\\\end{aligned}}$	${\begin{aligned}&{\text{max}}&&f(\mathbf {x} )=\mathbf {c} _{n}^{\mathrm {T} }\mathbf {x} _{n}+F_{0}\\&{\text{p.o.}}&&{\begin{bmatrix}A_{n}&I\end{bmatrix}}{\begin{bmatrix}\mathbf {x} _{n}\\\mathbf {x} _{b}\end{bmatrix}}=\mathbf {b} \\&&&\mathbf {x} _{n}\geq \mathbf {0} \\&&&\mathbf {x} _{b}\geq \mathbf {0} \\\end{aligned}}$

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

Ако имамо проблем у стандардном облику, са матрицом ограничења $A_{m\times n},(m<n)$, од свих променљивих можемо да изаберемо неких m променљивих, таквих да, ако остале променљиве изједначимо са нулом систем једначина ограничења може да се једниствено реши по изабраних m променљивих. Познато је да, да би систем једначина био решив, матрица коефицијената променљивих мора да буде инвертибилна, односно да има детерминанту различиту од 0. Ових m променљивих које задовољавају услов се називају базне променљиве, скуп базних променљивих се назива база, а квадратна матрица коефицијената базних променљивих се назива матрица базе.

${\begin{aligned}&{\begin{bmatrix}A_{n}&A_{b}\end{bmatrix}}{\begin{bmatrix}\mathbf {x} _{n}\\\mathbf {x} _{b}\end{bmatrix}}=\mathbf {b} &&\rightarrow &&{\begin{bmatrix}A_{n}&A_{b}\end{bmatrix}}{\begin{bmatrix}\mathbf {0} \\\mathbf {x} _{b}\end{bmatrix}}=\mathbf {b} &&\rightarrow &&A_{b}\mathbf {x} _{b}=\mathbf {b} &&\rightarrow &&\mathbf {x} _{b}=A_{b}^{-1}\mathbf {b} \\\end{aligned}}$

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

Ако вектоr коефицијената базних променљивих у функцији циља означимо са $\mathbf {c} _{b}$, тада ће вредност функције циља за дато базно допустиво решење бити једнака $\mathbf {c} _{b}^{\mathrm {T} }\mathbf {x} _{b}$, односно $\mathbf {c} _{b}^{\mathrm {T} }A_{b}^{-1}\mathbf {b}$.

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

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

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

${\begin{bmatrix}\mathbf {x} _{n}\\\mathbf {x} _{b}\end{bmatrix}}={\begin{bmatrix}\mathbf {0} \\\mathbf {b} \end{bmatrix}}$

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

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

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

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

Ако променљиве у ограничењима групишемо у базне и небазне, можемо методама линеарне алгебре (инверзија матрице или Гаус-Жорданова редукција) да трансформишемо систем једначина тако да матрица базе $A_{b}$ постане јединична матрица (што захтева канонски облик). Матрица небазних променљивих $A_{n}$ тада постаје матрица $A_{b}^{-1}A_{n}$, док вектор $\mathbf {b}$ постаје $A_{b}^{-1}\mathbf {b}$.

${\begin{aligned}&{\begin{bmatrix}A_{n}&A_{b}&\mathbf {b} \end{bmatrix}}&&\rightarrow &&{\begin{bmatrix}A_{n}^{*}&I&\mathbf {b} ^{*}\end{bmatrix}}&&\Leftrightarrow &&{\begin{bmatrix}A_{b}^{-1}A_{n}&I&A_{b}^{-1}\mathbf {b} \end{bmatrix}}\\\end{aligned}}$

Пошто канонски облик поставља услов да слободни чланови буду ненегативни, операција превођења у канонски облик у односну на дату базу ће успети ако је $A_{b}^{-1}\mathbf {b} \geq \mathbf {0}$. Дакле ако је овај услов задовољен можемо наставити са превођењем.

Превођење функције циља

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

У следећој формулацији ове операције $\mathbf {x} _{b}$ је вектор базних променљивих, a $\mathbf {x} _{n}$ је вектор небазних променљивих. Коефицијенти небазних променљивих су дати матрицом $A_{n}^{*}$, а слободни чланови вектором $\mathbf {b} ^{*}$.

${\begin{aligned}&f(\mathbf {x} )=\mathbf {c} _{n}^{\mathrm {T} }\mathbf {x} _{n}+\mathbf {c} _{b}^{\mathrm {T} }\mathbf {x} _{b}&&\rightarrow &&f(\mathbf {x} )=(\mathbf {c} _{n}^{\mathrm {T} }-\mathbf {c} _{b}^{\mathrm {T} }A_{n}^{*})\mathbf {x} _{n}+\mathbf {c} _{b}^{\mathrm {T} }\mathbf {b} ^{*}\\\end{aligned}}$

Резултат комплетне операције свођења у матричној форми

${\begin{aligned}&{\text{max}}&&f(\mathbf {x} )=\mathbf {c} _{n}^{\mathrm {T} }\mathbf {x} _{n}+\mathbf {c} _{b}^{\mathrm {T} }\mathbf {x} _{b}&&&&{\text{max}}&&f(\mathbf {x} )=(\mathbf {c} _{n}^{\mathrm {T} }-\mathbf {c} _{b}^{\mathrm {T} }A_{b}^{-1}A_{n})\mathbf {x} _{n}+\mathbf {c} _{b}^{\mathrm {T} }A_{b}^{-1}\mathbf {b} \\&{\text{p.o.}}&&{\begin{bmatrix}A_{n}&A_{b}\end{bmatrix}}{\begin{bmatrix}\mathbf {x} _{n}\\\mathbf {x} _{b}\end{bmatrix}}=\mathbf {b} &&\rightarrow &&{\text{p.o.}}&&{\begin{bmatrix}A_{b}^{-1}A_{n}&I\end{bmatrix}}{\begin{bmatrix}\mathbf {x} _{n}\\\mathbf {x} _{b}\end{bmatrix}}=A_{b}^{-1}\mathbf {b} \\&&&\mathbf {x} _{b}\geq \mathbf {0} &&&&&&\mathbf {x} _{b}\geq \mathbf {0} \\&&&\mathbf {x} _{n}\geq \mathbf {0} &&&&&&\mathbf {x} _{n}\geq \mathbf {0} \\\end{aligned}}$

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

${\begin{aligned}&{\begin{bmatrix}\mathbf {c} _{n}^{\mathrm {T} }&\mathbf {c} _{b}^{\mathrm {T} }&\mathbf {0} \\A_{n}&A_{b}&\mathbf {b} \\\end{bmatrix}}&&{\overset {\mathrm {e.t.r.} }{\rightarrow }}&&{\begin{bmatrix}{\mathbf {c} _{n}^{*}}^{\mathrm {T} }&0&-f\\A_{n}^{*}&I&\mathbf {b} ^{*}\end{bmatrix}}&&\Leftrightarrow &&{\begin{bmatrix}\mathbf {c} _{n}^{\mathrm {T} }-\mathbf {c} _{b}^{\mathrm {T} }A_{b}^{-1}A_{n}&0&-\mathbf {c} _{b}^{\mathrm {T} }A_{b}^{-1}\mathbf {b} \\A_{b}^{-1}A_{n}&I&A_{b}^{-1}\mathbf {b} \end{bmatrix}}\end{aligned}}$

Ако обратимо пажњу на услов $A_{b}^{-1}\mathbf {b} \geq \mathbf {0}$, онда је најефикасније прво израчунати слободне чланове, па ако задовољавају услов, израчунати остатак матрице.

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

Метода вештачких променљивих

Ова метода се још назива и методом великог M. Ако стандардним трансформацијама система једначина не можемо лако да добијемо канонски облик система ограничења онда ћемо у сваку једначину која одскаче од канонског облика додати по једну додатну променљиву. Ове нове променљиве зовемо вештачке (и обично означавамо са v) јер не постоје у оригиналном проблему. Зато ћемо у функцији циља вештачким променљивама доделити коефицијенте $-\mathrm {M}$, где је M неки много велики позитиван број (већи од било ког броја при поређењу). Овим осигуравамо да ће, због задатка максимизације, алгоритам за решавање сигурно овим променљивама доделити вредност 0, чиме се ова измена оргигиналног проблема поништава.

Проблем проширен вештачким променљивама у случају да свака једначина има по једну (што не мора да буде), изгледа овако:

${\begin{aligned}&{\text{max}}&&f(\mathbf {x} )=\mathbf {c} ^{\mathrm {T} }\mathbf {x} -{\text{M}}\sum _{i=1}^{m}v_{i}\\&{\text{p.o.}}&&A\mathbf {x} +\mathbf {v} =\mathbf {b} \\&&&\mathbf {x} \geq \mathbf {0} ,\mathbf {v} \geq \mathbf {0} \end{aligned}}$

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

$f(\mathbf {x} )=(\mathbf {c} ^{\mathrm {T} }+\mathrm {M} \cdot \mathbf {1} ^{\mathrm {T} }A)\mathbf {x} -\mathrm {M} \sum _{i=1}^{m}b_{i}$

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

Дуалност

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

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

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

Примал	Дуал
${\text{max}}\ f(\mathbf {x} )$	${\text{min}}\ \phi (\mathbf {y} )$
i - то ограничење	i - та променљива
типа $\leq$	$y_{i}\geq 0$
типа $\geq$	$y_{i}\leq 0$
типа $=$	$y_{i}$ неограничена по знаку
j - та проманљива	j - то ограничење
$x_{j}\geq 0$	типа $\geq$
$x_{j}\leq 0$	типа $\leq$
$x_{j}$ неограничена по знаку	типа $=$

Дуал проблема у симетричном облику

${\begin{aligned}&{\text{max}}&&f(\mathbf {x} )=\mathbf {c} ^{\mathrm {T} }\mathbf {x} &&&&{\text{min}}&&\phi (\mathbf {y} )=\mathbf {b} ^{\mathrm {T} }\mathbf {y} \\&{\text{p.o.}}&&A\mathbf {x} \leq \mathbf {b} &&\Leftrightarrow &&{\text{p.o.}}&&A^{\mathrm {T} }\mathbf {y} \geq \mathbf {c} \\&&&\mathbf {x} \geq \mathbf {0} &&&&&&\mathbf {y} \geq \mathbf {0} \\\end{aligned}}$

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

Теорија дуалности

Теорија дуалности изучава матемачка својства односа прималног и дуалног проблема.

Подразумевјући да примал представља проблем максимизације функције $f(\mathbf {x} )$, а дуал проблем минимизације функције $\phi (\mathbf {y} )$, они су повезани следећим својствима:

• Ако је x било које допустиво решење примала, а y било које допустиво решење дуала, тада је $f(\mathbf {x} )\leq \phi (\mathbf {y} )$. Ово се назива својство слабе дуалности.
• Ако је x допустиво решење примала које није оптимално и $f(\mathbf {x} )=\phi (\mathbf {y} )$, тада y није допустиво решење дуала.
• Ако су x и y допустива решења примала и дуала, и важи да је $f(\mathbf {x} )=\phi (\mathbf {y} )$, тада су тачке x и y оптимална решења примала и дуала. Ово својство важи и у супротном смеру.
• Примал има оптимално решење, ако и само ако дуал има оптимално решење, при чему су њихове вредности једнаке.
• Ако је функција циља примала неограничена одозго (отворен проблем), тада је допустива област дуала празна (ограничења ће бити некозистентна). А ако је дуал неограничен одоздо, тада је допустива област примала празна.

Дакле, ако су допустиве области примала и дуала непразне, оба проблема имају оптимално решење.

Алгоритми за решавање проблема ЛП

Алгортми промене базе

Симплекс алгоритам

Симплекс алгоритам, који је развио Џорџ Данциг 1947., решава проблеме линеарног програмирања тако што почиње од једног базног допустивог решења (темена допустиве области, која је облика вишедимензиналног полиедра), и генерише низ нових базних решења таквих да је свако следеће боље о претходног, док не стигне до оптималног решења.

Иако у најгорем случају Симплекс алгоритам има експоненцијалну сложеност, у пракси је прилично ефикасан, а показало се да ”насумичне” проблеме решава подједнако ефикасо као и практичне.

Criss-cross алгоритам

Као и Симплекс, и овај алгоритам се креће између базних решења. Али criss-cross алгоритам не мора да задржи допустивост база, већ може да оде и на недопустиав базна решења. Оавј алгоритам је као и Симплекс, експоненцијане сложености у најгорем случају.

Серангов алгоритам

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

Алгоритми који се крећу кроз унутрашњост

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

Хачијанов агортам је први алгоритам за решавање ЛП проблема који има полиномијалну сложеност у најгорем случају. Али је Симплекс и даље био ефикаснији осим у специјално направљеним случајевима. Касније је Кармаркар развио алгоритам бољих полиномијалних перформанси.

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

Види још

• Симплекс алгоритам
• Динамичко програмирање
• Транспортни проблем
• Оптимизација (математика)
• Операциона истраживања

Литература

• Dantzig, G.B.: Maximization of a linear function of variables subject to linear inequalities, 1947. Објављен на pp. 339–347 у Koopmans T.C. (ed.):Activity Analysis of Production and Allocation, New York-London 1951 (Wiley & Chapman-Hall)
• С. Крчевинац, М. Чангаловић, В. Ковачевић-Вујчић, М. Мартић, М. Вујошевић: Операциона истраживања 1, 3. издање, Београд (Факултет организационих наука). 2009. ISBN 978-86-7680-200-5.
• Nash, S.G., Sofer A.: "Linear and Nonlinear Programming", McGraw Hill. 1996. ISBN 007046.0655. ISBN 978-0070460652.
• Gass, S.I.: "Linear Programming: Methods and Applications". . Courier Dover Publications. 1985. ISBN 9780486432847. 
• Dantzig, G.B.: "Linear programming and extensions", . . Princeton University Press. 1998. ISBN 9780691059136. 
• Frederick, S.,H.,Lieberman, G.J. "Introduction to Operations Research, 6th edition, McGraw Hill, 1995
• Gondzio, Jacek; Terlaky, Tamás (1996). „3 A computational view of interior point methods”. Ур.: J. E. Beasley. Advances in linear and integer programming. Oxford Lecture Series in Mathematics and its Applications. 4. New York: Oxford University Press. стр. 103—144. MR 1438311. Postscript file at website of Gondzio and at McMaster University website of Terlaky.