Matemātika DU TSC
Nākamais: 3.3.2. Simpleksa metodes algoritms Augstāk: 3.3. Simpleksa metode Iepriekšējais: 3.3. Simpleksa metode

3.3.1. Izliektas kopas un lineāras programēšanas problēmu atrisināmība

Saskaņā ar iepriekšējā nodaļā teikto lineārās programmēšanas problēmas atrisinājums (divu dimensiju gadījumā) vienmēr atrodas vienā no pieļaujamā apgabala virsotnēm. Analoģisks rezultāts ir spēkā arī vispārīgā gadījumā. Aplūkosim minimizācijas problēmu mērķa funkcijai

$$Lx = \sum\limits_{i = 1}^n {k_j x_j \longrightarrow min }$$

ar $m$ ierobežojumiem (3.7), kurus pierakstīsim matricu formā:

$$Ax\leq b,$$ (3.10)

kur $A$ ir $n\times m$ matrica, $b=(b_{1};\ldots;b_{m})\in\mathbb{R}^{n}$. Pieļaujamais apgabals $F$, kuru nosaka nevienādība (3.10), ir izliekts daudzskaldnis telpā $\mathbb{R}^{n}$.

Pierādīsim, ka kopa $F\subset\mathbb{R}^n$ ir izliekta, t.i., kopa $F$ reizē ar jebkuriem diviem saviem punktiem $x_{1}$ un $x_{2}$ satur arī nogriezni ar galapunktiem $x_{1}$ un $x_{2}$:

$$[x_1;x_2]=\{x\in\mathbb{R}^{n}:\;{\alpha}x_{1}+(1-\alpha)x_{2}, 0\leq\alpha\leq 1\}.$$ (3.11)

Tiešām, ja $x={\alpha}x_{1}+(1-\alpha)x_{2}$, kur $0<\alpha<1$, tad

$$Ax=A[\alpha x_{1}+(1-\alpha)x_{2}]=\alpha Ax_{1}+(1-\alpha)Ax_{2} \leq\alpha b+(1-\alpha)b=b,$$

un, tā kā apgabals $F$ ir definēts ar nevienādību (3.10), tad visi nogriežņa (3.11) punkti pieder kopai $F$.

Viegli redzēt, ka kopas $F$ robeža sastāv no hiperplakņu

$$a_{i1}x_1+\ldots+a_{in}x_{n}=b_{i}\;\;(i=1,2,\ldots,n)$$ (3.12)

segmentiem.

Par $n$-dimensionāla daudzskaldņa $F$ virsotnēm sauc punktus, kuri pieder vismaz $n$ hiperplaknēm (3.12).

Triju (vai divu) dimensiju gadījumā, t.i., ja $n=3$ (vai $n = 2$), var sniegt uzskatāmu daudzskaldņa ģeometrisko interpretāciju. Ja $n=3$, tad $F$ ir daudzskaldnis, un vismaz triju plakņu, kuras veido $F$ robežu, kopējais punkts ir daudzskaldņa $F$ virsotne. Tā, piemēram, 3.2. zīmējumā attēlotā kopa $F$ - vienības kubs ar nošķeltu virsotni - izliekts daudzskaldnis ar $7$ skaldnēm un $10$ virsotnēm. Katra $F$ virsotne ir triju plakņu, kuras veido $F$ robežu, kopīgais punkts. Protams, var iedomāties daudzskaldni ($3$-dimensiju telpā) ar virsotni, kura ir vairāk nekā triju plakņu kopīgais punkts, piemēram, piramīdu, kuras pamatā ir četrstūris.

Lineārās programmēšanas teorijas pamatrezultāts saka, ka, ja lineārās programmēšanas problēmai ir atrisinājums, tad obligāti atradīsies šīs problēmas pieļaujamā apgabala $F$ virsotne, kas sakrīt ar šo atrisinājumu.

Šim faktam var sniegt uzskatāmu ģeometrisko interpretāciju, apskatot lineārās programmēšanas problēmas divu un triju dimensiju gadījumā. Tiešām, iedomāsimies $3$-dimensionālu izliektu daudzskaldni (- pieļaujamais apgabals $F$), kuru šķeļ plakne (- mērķa funkcijas līmeņvirsma). Paralēli pārnesot šo plakni, tā "pēdējā momentā" pieskaras apgabala $F$ robežai. Šis "moments", precīzāk sakot, pieskaršanās punkta koordinātas, atbilst ekstremālās problēmas atrisinājumam. Pārvietojot līmeņvirsmu (plakni) vienā virzienā, iegūstam minimizācijas problēmas atrisinājumu, bet, pārvietojot to pretējā virzienā, iegūstam maksimizācijas problēmas atrisinājumu. Mērķa funkcijas līmeņvirsmas pieskaršanās pieļaujamajam apgabalam var notikt šādi:

• līmeņvirsma pieskaras pieļaujamā apgabala virsotnei,
• līmeņvirsma pieskaras pieļaujamā apgabala šķautnei,
• līmeņvirsma pieskaras pieļaujamā apgabala skaldnei.

Otrajā un trešajā gadījumā ekstrēmu problēmai ir bezgalīgi daudz atrisinājumu, taču starp tiem noteikti ir arī pieļaujamā apgabala virsotnes.

Matemātika DU TSC
Nākamais: 3.3.2. Simpleksa metodes algoritms Augstāk: 3.3. Simpleksa metode Iepriekšējais: 3.3. Simpleksa metode