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

3.2.2 Minimuma gadījums

Atrisināsim grafiski šādu problēmu.

Problēma par optimālu pirkšanas plānu. Kādas valsts pieprasījums pēc naftas produktiem (miljonos tonnu) ir šāds:

Naftas produkts	Daudzums (miljonos tonnu)
Aviācijas degviela	1
Benzīns	5,5
Dīzeļdegviela	7

Tiek sastādīts šķidrās naftas pirkšanas plāns nākamajam gadam. Naftu iepērk no diviem atsevišķiem avotiem (apzīmēsim tos ar A un B). Naftas A un B sastāvs (procentos) ir šāds.

	Aviācijas degviela (%)	Benzīns (%)	Dīzeļdegviela (%)
Nafta no avota A	5	50	45
Nafta no avota B	15	35	50

Naftas no avota A cena par vienu tonnu ir $ $300$, bet naftas no avota B cena par tonnu - $ $280$. Cik jānopērk naftas no abiem avotiem, lai nodrošinātu valsti ar nepieciešamo degvielas daudzumu un samaksa par šķidro naftu būtu minimālā?

Atrisinājums. Formalizēsim doto problēmu.

Apzīmēsim:
$x_{1}$ - naftas no avota A daudzums (miljonos tonnu),
$x_{2}$ - naftas no avota B daudzums (miljonos tonnu).

Pirkšanas ierobežojumi:

$$\begin{array}{cccccc} \text{aviācijas degvielai -} & 0,05x_{1... ...gvielai -} & 0,45x_{1} & + & 0,5x_{2} & \geq & 7. \end{array}$$

Mērķa funkcija - pirktās naftas cena:

$$L=300x_{1}+280x_{2}.$$ (3.8)

Tātad matemātiski doto problēmu var formulēt šādi:

$$\begin{array}{l} L=300x_{1}+280x_{2}\longrightarrow min ,\ ... ...{1}+0,5x_{2}\geq 7,\ x_{1}\geq 0,\;\;x_{2}\geq 0. \end{array}$$ (3.9)

Nav būtiski, ka nevienādībās (3.9) figurē zīme $\geq$. Ja nevienādību (3.9) abas puses pareizinātu ar ``-1'', tad šīs nevienādības būtu formā (3.7).

Konstruējot pieļaujamo apgabalu ir mērķtiecīgi nevienādības (3.9) pārrakstīt šādi:

$$\begin{array}{l} 5x_{1}+15x_{2}\geq 100,\ 50x_{1}+35x_{2}\g... ...1}+50x_{2}\geq 700,\ x_{1}\geq 0,\;\;x_{2}\geq 0, \end{array}$$

jeb

$$\begin{array}{l} x_{2}\geq-\frac{1}{3}x_1+\frac{20}{3},\medsk... ...{10}x_1+14,\medskip\ x_{1}\geq 0,\;\;x_{2}\geq 0. \end{array}$$

Pieļaujamais apgabals ir attēlots 3.3. zīmējumā.

3.3. zīm. 

Tātad pieļaujamā apgabala robežu veido divas koordinātu līnijas un šādas taisnes:

taisne $CD$ ar vienādojumu $x_{2}=-\frac{1}{3}x_{1}+\frac{20}{3}$;

taisne $AB$ ar vienādojumu $x_{2}=-\frac{10}{7}x_{1}+\frac{110}{7}$;

taisne $BC$ ar vienādojumu $x_{2}=-\frac{9}{10}x_{1}+ 14$.

Ierobežojumiem atbilst kopas:

$G_{1}$ - pusplakne virs taisnes $CD$;
$G_{2}$ - pusplakne virs taisnes $AB$;
$G_{3}$ - pusplakne virs taisnes $BC$;
$G_{4}$ - pusplakne, kurā $x_{1}\geq 0$;
$G_{5}$ - pusplakne, kurā $x_{2}\geq 0$.

Pieļaujamais apgabals - kopu $G_{i}$ $(i=1,2,3,4,5)$ šķēlums $F= \bigcap\limits_{i=1}^5G_{i}$ - bezgalīgs daudzstūris.

Mērķa funkcijas līmeņlīniju vienādojums

$$300x_{1}+280x_{2}=c_1$$

vai

$$x_{2}=-\frac{15}{14}x_{1}+ c.$$

Kad $c = 0$, līmeņlīnija iet caur punktu $O$, kad $c=10$, līmeņlīnija ieņem stāvokli $GH$. Secinājums: palielinot parametru $c$, līmeņlīnijas tiek paralēli pārnestas uz augšu. Ir skaidrs, ka eksistē parametra $c$ vērtība, kuru apzīmēsim ar $c_{\ast}$, kurai līmeņlīnija

$$x_{2}=-\frac{15}{14}x_{1}+c_{\ast}$$

pieskarsies apgabalam $F$ no apakšas un šis pieskaršanās punkts arī būs mūsu problēmas minimuma punkts. Lai atrastu pieskaršanās punktu, sakārtosim koeficientus pie $x_1$ taišņu $CD$, $AB$, $BC$, $GH$ vienādojumos augošā secībā:

$$-\frac{10}{7}<-\frac{15}{14}<-\frac{9}{10}<-\frac{1}{3}.$$

Jo mazāks ir koeficients (bet lielāks pēc moduļa), jo attiecīgā taisne ir slīpāka. Acīmredzot, taisne ar koeficientu $-\frac{15}{14}$ pieskaras apgabalam $F$ taišņu

$$x_{2}= \;-\frac{10}{7}x_{1}+\frac{110}{7},$$

$$x_{2}= \;-\frac{9}{10}x_{1}+14$$

krustpunktā. Risinot divu lineāro vienādojumu sistēmu, iegūstam atbildi (un līdz ar to arī optimālo šķidrās naftas pirkšanas plānu):

$$x_{1}= \;3\frac{9}{37}\;\; ,$$

$$x_{2}= \;11\frac{3}{37}\;\; .$$

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