Grundläggande genomförbar lösning

I teorin för linjär programmering är en grundläggande genomförbar lösning ( BFS ) en lösning med en minimal uppsättning variabler som inte är noll. Geometriskt motsvarar varje BFS ett hörn av polyedern av möjliga lösningar. Om det finns en optimal lösning, så finns det en optimal BFS. För att hitta en optimal lösning är det därför tillräckligt att överväga BFS-erna. Detta faktum används av simplexalgoritmen , som i huvudsak går från en viss BFS till en annan tills en optimal hittas.

Definitioner

Preliminärer: ekvationsform med linjärt oberoende rader

För definitionerna nedan presenterar vi först det linjära programmet i den så kallade ekvationsformen :

maximera ${\textstyle \mathbf {c^{T}} \mathbf {x} }$

med förbehåll för $A\mathbf {x} =\mathbf {b}$ och $\mathbf {x} \geq 0$

var:

• $\mathbf {c^{T}}$ och $\mathbf {x}$ är vektorer av storlek n (antalet variabler);
• $\mathbf {b}$ är en vektor med storleken m (antalet begränsningar);
• $A$ är en m -by- n matris;
• $\mathbf {x} \geq 0$ betyder att alla variabler är icke-negativa.

Alla linjära program kan konverteras till en ekvationsform genom att lägga till slackvariabler .

Som ett preliminärt saneringssteg verifierar vi att:

• Systemet $A\mathbf {x} =\mathbf {b}$ har minst en lösning (annars har hela LP-skivan ingen lösning och det finns inget mer att göra);
• Alla m rader i matrisen $A$ är linjärt oberoende, dvs dess rangordning är m (annars kan vi bara ta bort redundanta rader utan att ändra LP).

Möjlig lösning

En möjlig lösning av LP är vilken vektor som helst $\mathbf {x} \geq 0$ så att $A\mathbf {x} =\mathbf {b}$ . Vi antar att det finns minst en genomförbar lösning. Om m = n så finns det bara en möjlig lösning. Typiskt m < n , så systemet $A\mathbf {x} =\mathbf {b}$ har många lösningar; varje sådan lösning kallas en genomförbar lösning av LP.

Grund

En grund för LP är en icke-singular submatris av A, med alla m rader och endast m < n kolumner.

Ibland används termen bas inte för själva delmatrisen, utan för uppsättningen av index för dess kolumner. Låt B vara en delmängd av m -index från {1,..., n }. Beteckna med $A_{B}$ den kvadratiska m -by- m -matrisen gjord av de m kolumnerna i $A$ indexerade av B . Om $A_{B}$ är nonsingular , är kolumnerna som indexeras av B en bas för kolumnutrymmet för $A$ . I det här fallet kallar vi B en grund för LP:n.

Eftersom rangordningen för $A$ är m , har den minst en bas; eftersom $A$ har n kolumner, har den högst ${\binom {n}{m}}$ baser.

Grundläggande genomförbar lösning

Givet en bas B , säger vi att en genomförbar lösning $\mathbf {x}$ är en grundläggande genomförbar lösning med bas B om alla dess icke-nollvariabler indexeras med B , det vill säga för alla $j\not \in B:~~x_{j}=0$ .

Egenskaper

1. En BFS bestäms endast av LP:ns begränsningar (matrisen $A$ och vektorn ${\displaystyle \mathbf {b} } )$ ; det beror inte på optimeringsmålet.

2. Per definition har en BFS högst m icke-nollvariabler och minst n - m nollvariabler. En BFS kan ha mindre än m icke-nollvariabler; i så fall kan den ha många olika baser, som alla innehåller indexen för dess icke-nollvariabler.

3. En möjlig lösning $\mathbf {x}$ är grundläggande om-och-bara-om kolumnerna i matrisen $A_{K}$ är linjärt oberoende, där K är mängden index av elementen som inte är noll i $\mathbf {x}$ .

4. Varje bas bestämmer en unik BFS: för varje bas B av m -index finns det högst en BFS $\mathbf {x_{B}}$ med bas B . Detta beror på att $\mathbf {x_{B}}$ måste uppfylla kravet ${\displaystyle A_{B}\mathbf {x_{B}} =b} ,$ och per definition av basen är matrisen $A_{B}$ icke-singular, så begränsningen har en unik lösning:

$\mathbf {x_{B}} ={A_{B}}^{-1}\cdot b$

Motsatsen är inte sant: varje BFS kan komma från många olika baser. Om den unika lösningen av $\mathbf {x_{B}} ={A_{B}}^{-1}\cdot b$ uppfyller icke-negativitetsbegränsningarna $\mathbf {x_{B}} \geq 0$ , då kallas B en genomförbar bas .

5. Om ett linjärt program har en optimal lösning (dvs. det har en genomförbar lösning och uppsättningen av genomförbara lösningar är begränsad), så har det en optimal BFS. Detta är en konsekvens av Bauers maximala princip : målet för ett linjärt program är konvext; uppsättningen möjliga lösningar är konvex (det är en skärningspunkt av hyperrymden); därför uppnår målet sitt maximum i en extrem punkt av uppsättningen av genomförbara lösningar.

Eftersom antalet BFS-s är ändligt och begränsat av ${\displaystyle {\binom {n}{m}}} ,$ kan en optimal lösning för alla LP hittas i ändlig tid genom att bara utvärdera objektivfunktionen i alla ${\binom {n}{m}}$ BFS-s. Detta är inte det mest effektiva sättet att lösa en LP; simplexalgoritmen undersöker BFS-erna på ett mycket mer effektivt sätt .

Exempel

Tänk på ett linjärt program med följande begränsningar:

${\begin{aligned}x_{1}+5x_{2}+3x_{3}+4x_{4}+6x_{5}&=14\\x_{2}+3x_{3}+5x_{ 4}+6x_{5}&=7\\\forall i\in \{1,\ldots ,5\}:x_{i}&\geq 0\end{aligned}}$

Matrisen A är:

$A={\begin{pmatrix}1&5&3&4&6\\0&1&3&5&6\end{pmatrix}}~~~~~\mathbf {b} =(14~~7)$

Här är m =2 och det finns 10 delmängder av 2 index, dock är inte alla baser: mängden {3,5} är inte en bas eftersom kolumnerna 3 och 5 är linjärt beroende.

Mängden B ={2,4} är ​​en bas, eftersom matrisen $A_{B}={\begin{pmatrix}5&4\\1&5\end{pmatrix}}$ är icke-singular.

Den unika BFS som motsvarar denna bas är $x_{B}=(0~~2~~0~~1~~0)$ .

Geometrisk tolkning

Uppsättningen av alla möjliga lösningar är en skärningspunkt av hyperrymder . Därför är det en konvex polyeder . Om det är avgränsat är det en konvex polytop . Varje BFS motsvarar en vertex av denna polytop.

Grundläggande genomförbara lösningar för det dubbla problemet

Som nämnts ovan definierar varje bas B en unik grundläggande genomförbar lösning $\mathbf {x_{B}} ={A_{B}}^{-1}\cdot b$ . På ett liknande sätt definierar varje bas en lösning till det dubbla linjära programmet :

minimera ${\textstyle \mathbf {b^{T}} \mathbf {y} }$

med förbehåll för $A^{T}\mathbf {y} \geq \mathbf {c}$ .

Lösningen är $\mathbf {y_{B}} ={A_{B}^{T}}^{-1}\cdot c$ .

Att hitta en optimal BFS

Det finns flera metoder för att hitta en BFS som också är optimal.

Använder simplexalgoritmen

I praktiken är det enklaste sättet att hitta en optimal BFS att använda simplexalgoritmen . Den behåller, vid varje punkt av dess exekvering, en "nuvarande bas" B (en delmängd av m av n variabler), en "nuvarande BFS" och en "nuvarande tablå". Tabellen är en representation av det linjära programmet där de grundläggande variablerna uttrycks i termer av de icke-grundläggande:

$${\begin{aligned}x_{B}&=p+Qx_{N}\\z&=z_{0}+r^{T }x_{N}\end{aligned}}$$

där $x_{B}$ är vektorn för m basvariabler, $x_{N}$ är vektorn för n icke-grundläggande variabler, och $z$ är maximeringsmålet . Eftersom icke-grundläggande variabler är lika med 0, är ​​den aktuella BFS $p$ , och det aktuella maximeringsmålet är $z_{0}$ .

Om alla koefficienter i $r$ är negativa är $z_{0}$ en optimal lösning, eftersom alla variabler (inklusive alla icke-grundläggande variabler) måste vara minst 0, så den andra raden antyder $z\leq z_{0}$ .

Om några koefficienter i $r$ är positiva kan det vara möjligt att öka maximeringsmålet. Till exempel, om $x_{5}$ är icke-grundläggande och dess koefficient i $r$ är positiv, kan en ökning av den över 0 göra $z$ större. Om det är möjligt att göra det utan att bryta mot andra begränsningar, så blir den ökade variabeln grundläggande (den "träder in i basen"), medan någon basvariabel minskas till 0 för att behålla likhetsbegränsningarna och blir därmed icke-grundläggande (den "går ut grunden").

Om denna process görs noggrant, är det möjligt att garantera att $z$ ökar tills den når en optimal BFS.

Konvertera vilken optimal lösning som helst till en optimal BFS

I värsta fall kan simplexalgoritmen kräva exponentiellt många steg att slutföra. Det finns algoritmer för att lösa en LP i svagt polynomisk tid, såsom ellipsoidmetoden ; dock returnerar de vanligtvis optimala lösningar som inte är grundläggande.

Men med tanke på vilken optimal lösning som helst på LP:n är det lätt att hitta en optimal genomförbar lösning som också är grundläggande .

Att hitta en bas som är både primaloptimal och dubbeloptimal

En bas B för LP kallas dual-optimal om lösningen $\mathbf {y_{B}} ={A_{B}^{T}}^{-1 }\cdot c$ är en optimal lösning för det dubbla linjära programmet, det vill säga det minimerar ${\textstyle \mathbf {b^{T}} \mathbf {y} }$ . I allmänhet är en primal-optimal bas inte nödvändigtvis dubbeloptimal, och en dubbeloptimal bas är inte nödvändigtvis primal-optimal (i själva verket kan lösningen av en primal-optimal bas till och med vara omöjlig för den dubbla, och vice versa ).

Om både $\mathbf {x_{B}} ={A_{B}}^{-1}\cdot b$ är en optimal BFS för den primära LP:n, och ${\displaystyle \mathbf {y_{B}} ={A_{B}^{T}}^{-1}\cdot c} är$ en optimal BFS för den dubbla LP:n, då bas B kallas PD-optimal . Varje LP med en optimal lösning har en PD-optimal bas, och den hittas av Simplex-algoritmen . Dess körtid är dock exponentiell i värsta fall. Nimrod Megiddo bevisade följande satser:

• Det finns en starkt polynomisk tidsalgoritm som matar in en optimal lösning till den primära LP:n och en optimal lösning till den dubbla LP:n, och returnerar en optimal bas.
• Om det finns en starkt polynomisk tidsalgoritm som matar in en optimal lösning till endast den primära LP (eller endast den dubbla LP) och returnerar en optimal bas, så finns det en starkt polynomisk tidsalgoritm för att lösa alla linjära program (den senare är en berömt öppet problem).

Megiddos algoritmer kan exekveras med hjälp av en tablå, precis som simplexalgoritmen.

externa länkar

• Hur man går från en optimal genomförbar lösning till en optimal grundläggande genomförbar lösning . Paul Robin, Operations Research Stack Exchange.