Från Rilpedia

Du har inte behörighet att redigera denna sida, av följande anledning:

Du kan se och kopiera denna sidas källtext:

<noinclude>{{rpsv.from.wpsv}}</noinclude>'''LP-problem; Linjärprogrammeringsproblem''' är en typ av [[optimeringsproblem]] med den egenskapen att målfunktionen och samtliga bivillkor är linjära funktioner. LP-problemen betraktas inom [[optimeringslära|optimeringsläran]] som förhållandevis lätta även om de i praktiska tillämpningar endast i sällsynta fall kan lösas utan datorstöd (då t.ex med hjälp av [[simplexmetoden]]) Det generella LP-problemet kan skrivas som: <math> \mbox{min z} = \sum_{j=i}^n c_jx_j </math> <math> \mbox{då} \qquad\ \sum_{j=i}^n a_{i,i}x_j \le b_i, \quad i = 1,...m </math> Där z är målfunktionen som skall optimeras, variablerna <math> x_j </math> är de n-stycken beslut som ska fattas, <math> c_j </math> är kostnaderna för besluten och <math> x_(i,j) </math> och <math> x_i </math> definerar de m-stycken [[bivillkor]] (krav) som måste vara uppfyllda. ==Standardform== Standardformen för ett LP-problem är en omskrivning av problemet så att samtliga variabler är ickenegativa samt att samtliga bivillkor formulerats som likhetsvillkor. Det sistnämnda kan uppnås genom att icke-negativa [[slackvariabler]] introduceras i samtliga olikhetsvillkor där slackvariabeln utjämnar likheten. Exempelvis kan olikheten: <math> x_1 + x_2 \le 5 </math> Skrivas som: <math> x_1 + x_2 + a_1 = 5 </math> Där <math> a_1 </math> är en ickenegativ slackvariabel som kan betraktas som kvarvarande frihet. ''icke-negativitet'' för alla variabler uppnås genom variabelbyte då varibler <math> x_1 \le 0 </math> ersätts med <math> y_1 = -x_1 </math> och fria varibler delas i två variabler. dvs <math> x_1 = y_1 - y_2 </math> där <math> y_1 </math> kommer vara noll när <math> x_1 \le 0 </math> och <math> y_2 </math> kommer vara noll när <math> x_1 \ge 0 </math>. Båda de nya variablerna är dock ickenegativa emedans <math> x_1 </math> var fri. Omskrivning på standardform innebär inte sällan att antalet variabler ökar betydligt vilket givetvis kan försvåra beräkningarna men då [[LP-problem]] i praktisk sammanhang nästan uteslutande löses med datorstöd är detta ett litet pris att betala för att kunna använda generella algoritmer som t.ex [[simplexmetoden]]. ==Baslösning== Baslösningar är ett sätt att vid lösningen av LP-problem beskriva extremlösningar (hörnpunkter i definitionsmängden). Baslösningar används bl.a. av [[simplexmetoden]] för att systematiskt avsöka extrempunkterna. För ett LP-problem skrivit på standardform kan alla lösningar tecknas som en [[vektor]] av problemets samtliga variabler (även slackvariabler). Ur ett ekvationssytem (här på matrisform A är en n*m-matris) Ax = b erhålles en baslösning om n-m variabler sätts till 0 och det kvarvande ekvationssystemet löses. Här kallas de variabler som löses ut för ''basvariabler'' och då de entydigt bestämmer hörnpunkten, övriga variabler (som är noll) kalls ''icke-basvariabler'' eller ibland nollvariabler. Speciellt är en baslösning där alla element i vektorn är icke-negativa en ''tillåten baslösning'' dvs den uppfyller bivillkoren för LP-problemet. En baslösning är ''degenererad'' om någon av basvariablerna beräknats till noll dvs om andra variabler kunde väljas som icke-basvariabler och ändå generera samma hörnpunkt. ==Egenskaper== Det tillåtna området (de punkter: (<math> x_1,\; x_2,\; ...\; x_n </math>) som satsiferar samtliga bivillkor) till ett LP-problem kommer alltid vara en [[konvex mängd]]. Denna egenskap följer direkt av att bivillkoren är linjära. Denna egenskap tillsammans med målfunktionens liniarietmmedför att lokala optima även är globala och leder fram till [[Linjärprogrammeringens fundamentalsats]]. [[Kategori:Optimeringslära]] [[af:Lineêre programmering]] [[bs:Linearno programiranje]] [[ca:Programació lineal]] [[cs:Lineární programování]] [[de:Lineare Optimierung]] [[en:Linear programming]] [[es:Programación lineal]] [[fa:برنامه‌ریزی خطی]] [[fr:Programmation linéaire]] [[he:תכנון לינארי]] [[hu:Lineáris optimalizálás]] [[id:Pemrograman linier]] [[it:Programmazione lineare]] [[ja:線形計画問題]] [[ko:선형 계획법]] [[nl:Lineair programmeren]] [[pl:Programowanie liniowe]] [[pt:Programação linear]] [[ru:Линейное программирование]] [[scn:Prugrammazzioni liniàri]] [[sl:Linearno programiranje]] [[sr:Линеарно програмирање]] [[th:กำหนดการเชิงเส้น]] [[tr:Doğrusal programlama]] [[uk:Лінійне програмування]] [[ur:لکیری برمجہ]] [[vi:Quy hoạch tuyến tính]] [[zh:线性规划]]

Tillbaka till LP-problem.