Matemātika DU TSC
Nākamais: 3.2.2 Minimuma gadījums Augstāk: 3.2. Lineārās programēšanas uzdevumu risināšanas grafiskā Iepriekšējais: 3.2. Lineārās programēšanas uzdevumu risināšanas grafiskā

3.2.1. Apraksts

Meģināsim analizēt lineārās programmēšanas uzdevuma ģeometrisko saturu. Nevienādības (3.7) definē daudzskaldņa tipa apgabalu $n$-dimensiju telpā $\mathbb{R}^{n}$. Tiešam, pirmā no nevienādībam (3.7) definē telpas $\mathbb{R}^{n}$ pustelpu, kura atrodas vienā pusē attiecībā pret hiperplakni

$$a_{11}x_{1}+\cdots+a_{1n}x_{n}=b_{1}.$$

Apzīmēsim šo hiperplakni ar $G_{1}$. Otrā no nevienādībam (3.7) definē pustelpu $G_{2}$ utt. Rezultātā iegūstam telpisku figūru $F=G_{1}\cap\cdots\cap G_{n}$, kura veido daudzskaldni telpā $\mathbb{R}^{n}$. Šī daudzskaldņa robeža sastāv no hiperplakņu

$$a_{i1}x_{1}+\cdots+a_{1n}x_{n}=b_{i}\;\;(i=1,2,\ldots,m)$$

segmentiem. Kopu $F$ sauc par pieļaujamo apgabalu, jo par lineārās programmēšanas uzdevuma atrisinājumu var būt tikai punkts $p=(x_{1};\ldots;x_{n})$, kurš pieder kopai $F$.

Piemēram, 1. problēmā kopas G$_{n }$ ir šādas:

$$G_1= \;\{(x_{1};x_{2}):\;5x_{1}+3x_{2}\leq 105 \},$$

$$G_2= \;\{(x_{1};x_{2}):\;2x_{1}+4x_{2}\leq 70\},$$

$$G_3= \;\{(x_{1};x_{2}):\;x_{1}\geq 0,\;-\infty <x_{2}<+\infty\},$$

$$G_4= \;\{(x_{1};x_{2}):\;x_{2}\geq 0,\;-\infty<x_{1}<+\infty\}.$$

Katra no šīm kopām ir $(x_{1};x_{2})$-plaknes pusplakne. Pieļaujamais apgabals $F=G_{1}\cap G_{2}\cap G_{3}\cap G_{4}$ ir daudzstūris $ACDO$ (skat. 3.1. zīm.).

3. problēma. Sniegsim vēl vienu pieļaujamā apgabala piemēru. Aplūkosim problēmu $3$-dimensiju telpā

$$Lx=k_1x_1+k_2x_2+k_3x_3\longrightarrow$$

ar $7$ ierobežojumiem nevienādību veidā:

$$\begin{array}{l} x_1\geq 0,\;\;x_1\leq 1, \ x_2\geq 0,\;\;x... ...\;x_2\leq 1, \ x_{1}+x_{2}+x_{3}\leq\frac{5}{2}. \end{array}$$

Katra no šīm nevienādībām definē pustelpu $3$-dimensiju Eiklīda telpā $\mathbb{R}^{3}$. Šo $7$ pustelpu kopējā daļa ir vienības kubs bez virsotnes (skat. 3.2. zīm.).

3.2. zīm. 

Gadījumā, kad telpas dimensiju skaits lielāks nekā $3$, izpildīt $2$-dimensionālu zīmējumu ir sarežģīti, un tas nebūtu informatīvs (pamēģiniet izveidot $3$-dimensionāla kuba $1$-dimensionālu zīmējumu).Tāpēc lineārās programmēšanas uzdevuma risināšanas grafiskā metode pārsvarā tiek lietota, risinot uzdevumus $2$ vai $3$ dimensiju gadījumā.

Grafiskās metodes lietošanas shēma ir šāda. Tiek attēlots pieļaujamais apgabals $F$, kuru veido daudzstūris $2$ dimensiju gadījumā, un daudzskaldnis $3$ dimensiju gadījumā. Tiek attēlota mērķa funkcijas līmeņlīniju kopa $2$ dimensiju gadījumā un līmeņvirsmu kopa $3$ dimensiju gadījumā, t.i., punktu $(x_{1},\ldots,x_{n})\in\mathbb{R}^{n}$, kuriem

$$Lx=k_{1}x_{1}+\cdots+k_{n}x_{n}=c=const.,$$

kopa, ja $n = 2$ vai $n=3$. Ja kāda līmeņlīnija (vai attiecīgi līmeņvirsma) dotajam $c$ ir konstruēta, tad pārējās līmeņlīnijas (vai attiecīgi līmeņvirsmas) iegūst no dotās ar paralēlās pārneses palīdzību. Mainot $c$, nosaka mērķa funkcijas vērtību palielināšanās virzienu (ja ir jāatrod mērķa funkcijas maksimums) vai mērķa funkcijas vērtību samazināšanās virziens (ja ir jāatrod mērķa funkcijas minimums). Visbeidzot, maksimuma problēmas gadījumā nosaka maksimālo parametra $c$ vērtību $c_{max}$, pie kuras līmeņlīnijai (vai attiecīgi līmeņvirsmai) ir kopīgs punkts ar pieļaujamo apgabalu. Šī kopīgā punkta koordinātas arī ir apskatāmās maksimuma problēmas atrisinājums. Ievietojot atrastās koordinātas mērķa funkcijas izteiksmē, iegūst tās maksimālo vērtību pie dotajiem ierobežojumiem. Minimuma problēmas gadījumā nosaka minimālo parametra $c$ vērtību $c_{min}$, pie kuras līmeņlīnijai (vai attiecīgi līmeņvirsmai) ir kopīgs punkts ar pieļaujamo apgabalu. Šī kopīgā punkta koordinātas arī ir apskatāmās minimuma problēmas atrisinājums. Ievietojot atrastās koordinātas mērķa funkcijas izteiksmē, iegūst tās minimālo vērtību pie dotajiem ierobežojumiem.

Matemātika DU TSC
Nākamais: 3.2.2 Minimuma gadījums Augstāk: 3.2. Lineārās programēšanas uzdevumu risināšanas grafiskā Iepriekšējais: 3.2. Lineārās programēšanas uzdevumu risināšanas grafiskā