Matemātika DU TSC
Nākamais: 3.2. Lineārās programēšanas uzdevumu risināšanas grafiskā Augstāk: 3. LINEĀRĀS PROGRAMMĒŠANAS UZDEVUMI Iepriekšējais: 3. LINEĀRĀS PROGRAMMĒŠANAS UZDEVUMI

3.1. Ievads

1. problēma. Aplūkosim $(x_1;x_2)$-plaknes apgabalu, kuru nosaka nevienādības:

$$5x_{1}+3x_{2}\leq 105,$$ (3.1)

$$2x_{1}+4x_{2}\leq 70,$$ (3.2)

$$x_{1}\geq 0,\;\;x_{2}\geq 0.$$ (3.3)

Šis apgabals ir attēlots 3.1. zīmējumā. Plaknes $(x_{1};x_{2})$ punkti, kuri apmierina nevienādību $5x_{1}+3x_{2}\leq 105$, atrodas zem taisnes $DB$, kuras vienādojums ir $5x_{1}+3x_{2}=105$; punkti, kuri apmierina nevienādību $2x_{1}+4x_{2}\leq 70$, atrodas zem taisnes $AE$, kuras vienādojums ir $2x_{1}+4x_{2}=70$. Ņemot vērā nosacījumus $x_{1}\geq 0$ un $x_{2}\geq 0$, secinām, ka apgabals, kuru nosaka nevienādības (3.1), (3.2) un (3.3), ir daudzstūris $ACDO$.

3.1. zīm. 

Aplūkosim taišņu saimi

$$200x_{1}+160x_{2}=\alpha,$$ (3.4)

parametram $\alpha$ piešķirot dažādas vērtības. Ja $\alpha=0$, tad (3.4) nosaka taisni ar vienādojumu

$$200x_{1}+160x_{2}=0$$

jeb

$$5x_{1}+4x_{2}=0.$$

Šī taisne iet caur punktu $O$ un 3.1. zīmējumā ir apzīmēta ar $GH$.

Jautājums. Kādām parametra $\alpha$ vērtībām taisne (3.4) satur kopējus punktus ar apgabalu $ACDO$?

Atrisinājums. Ja $\alpha=0$, tad taisne (3.4) ir attēlota 3.1. zīmējumā. Palielinot parametru $\alpha$, šī taisne virzās paralēli sev bultiņas virzienā, šķērsojot apgabalu $ACDO$. Acīmredzami eksistē parametra $\alpha$ vērtība $\alpha_0$, kurai taisne (3.4) iet caur punktu $C$ (punkts $C$ ir daudzstūra $ACDO$ virsotne). Pie turpmākas parametra $\alpha$ palielināšanas taisne pārvietojas uz augšu - bultiņas virzienā - un tai vairs nav kopēju punktu ar apgabalu $ACDO$.

Atbilde. Maksimālā parametra $\alpha$ vertība, kurai taisnei $200x_{1}+160x_{2}=\alpha$ ir kopējie punkti ar apgabalu $ACDO$, ir vērtība $\alpha_0$, kurai taisne (3.4) iet caur punktu $C$.

Lai atrastu $\alpha_0$ vērtību, vispirms aprēķināsim punkta $C$ koordinātas. Tā kā $C$ ir taišņu $5x_{1}+3x_{2}=105$ un $2x_{1}+4x_{2}=70$ krustpunkts, tad, atrisinot lineāru vienādojumu sistēmu

$$\left\{ {\begin{array}{ccc} 5x_1 + 3x_2 & = &0, \\ 2x_1 + 4x_2 & = &0, \\ \end{array}} \right.$$

atrodam, ka punkta $C$ koordinātas ir $x_{1}=15$, $x_{2}=10$. Ievietojot šīs koordinātas vienādojumā (3.4), iegūsim:

$$\alpha_0=200\cdot 15+160\cdot 10=4600.$$

2. problēma. Uzņēmums ražo $2$ veidu izstrādājumus, kurus apzīmēsim ar $X_{1}$ un $X_{2}$. Lai saražotu izstrādājuma $X_{1}$ vienību, ir vajadzīgas $5$ darba stundas konveijeru cehā un $2$ darba stundas komplektēšanas cehā. Lai saražotu izstrādātu izstrādājuma $X_{2}$ vienību, ir vajadzīgas $3$ darba stundas konveijeru cehā un $4$ darba stundas komplektēšanas cehā. Tehnoloģisku iemeslu dēļ mēnesī ir iespējams izmantot tikai $105$ darba stundas konveijeru cehā un $70$ darba stundas komplektēšanas cehā. Izstrādājuma $X_{1}$ vienības cena ir Ls $200$, bet izstrādājuma $X_{2}$ vienības cena ir Ls $160$.

Jautājums. Cik izstrādājumu $X_{1}$ un $X_{2}$ vienību ir jasaražo, lai ienākums būtu maksimāls?

Kas saista 1. problēmu, kurai ir ģeometriski-algebrisks raksturs, un 2. problēmu, kurai ir ekonomisks raksturs? Abās problēmās figurē vienādi skaitļi $2$, $3$, $4$, $5$, $70$, $105$. Un vēl?

No pirmā acu uzmetiena liekas, ka ir jāražo tikai izstrādājumi $X_{1}$, jo tie maksā dārgāk. Dalām skaitli $105$ ar $5$ un iegūstam, ka mēnesī konveijeru cehā var apstrādāt 1. izstrādājuma $21$ vienību. Dalot $70$ ar $2$, iegūstam, ka komplektēšanas cehā var apstrādāt $x_{1}$ izstrādājuma $35$ vienības. Izrādās, ka uzņēmums mēneša laikā var saražot 1. izstrādājuma $21$ vienību, noslogojot konveijeru cehu, bet tad komplektēšanas cehs nebūs noslogots $28$ stundas (aprēķins: $21\cdot 2=42$, $70-42=28$). Ienākuma aprēķins: $21\cdot 2000=4200$ Ls. Bet vai nevarētu kopā ar 1. izstrādājumu ražot arī zināmu daudzumu 2. izstrādājuma, lai noslogotu ražošanu? Vai tādā gadījumā ienākums nebūtu lielāks?

Tagad formulēsim 2. problēmu matemātiski. Apzīmēsim saražoto izstrādājuma $X_{1}$ daudzumu ar $x_{1}$, bet saražoto izstrādājuma $X_{2}$ daudzumu ar $x_{2}$. Tad ienākumu var aprēķināt pēc šādas formulas:

$$P=200x_{1}+160x_{2}.$$

Acīmredzot, $x_{1}$, $x_{2}$ un $P$ nevar pieņemt pēc patikas lielas vērtības, jo ražošanas procesam ir ierobežojumi. Pirmais ierobežojums:

$$5x_{1}+3x_{2}\leq 105,$$

jo konveijeru cehā abu izstrādājumu ražošanai var izmantot ne vairāk kā $105$ darba stundas mēnesī. Otrais ierobežojums:

$$2x_{1}+4x_{2}\leq 70,$$

jo komplektēšanas cehu abu izstrādājumu ražošanai var izmantot ne vairāk ka $70$ darba stundas mēnesī. Papildus ierobežojumi:

$$x_{1}\geq 0,\;\; x_{2}\geq 0$$

(nevar saražot negatīvu daudzumu izstrādājumu).

Tātad ir jāatrisina šāda matemātiska problēma:

$$\begin{array}{c} P=200x_{1}+160x_{2}\longrightarrow max, \ ... ...{1}+4x_{2}\leq 70, \ x_{1}\geq 0,\;\;x_{2}\geq 0, \end{array}$$ (3.5)

t.i., jāatrod lineāras funkcijas maksimums ar ierobežojumiem lineāru nevienādību formā, citiem vārdiem sakot, ir jāatrisina tā saucamais lineārās programmēšanas uzdevums.

Par lineārās programmēšanas uzdevumu sauc lineāras funkcijas ekstrēma atrašanu, t.i.,

$$Lx=k_{1}x_{1}+k_{2}x_{2}+\cdots+k_{n}x_{2}\longrightarrow ,$$ (3.6)

pie lineāriem ierobežojumiem:

$$\begin{array}{ccccc} a_{11}x_{1}+&\cdots& +a_{1n}x_n & \leq &... ...a_{n1}x_{1}+&\cdots& +a_{nn}x_n & \leq & b_n\/. \ \end{array}$$ (3.7)

Funkciju (3.6) sauc par mērķa funkciju.

Piemēram, 1. problēmā funkcija

$$L=200x_{1}+160x_{2}$$

ir mērķa funkcija, kurai tiek meklēts minimums pie lineāriem ierobežojumiem:

$$\begin{array}{ccccc} 5x_1&+&3x_2&\leq& 105\/, \ 2x_1&+&4x_2... ...\/, \ -x_1&&&\leq& 0\/, \ &&-x_2&\leq& 0\/. \ \end{array}$$

Šeit $n = 2$ (- mainīgo skaits), $m = 4$ (- ierobežojumu skaits), nevienādību (3.7) labajā pusē atrodošies skaitļi veido vektoru $b=(105;70;0;0)$, bet nevienādību (3.7) koeficienti $a_{ij}$ veido $2\times 4$ matricu

$$A=\left\Vert{\begin{array}{cc} 5&3 \ 2&4 \ -1&0 \ 0&-1 \ \end{array}} \right\Vert.$$

Matemātika DU TSC
Nākamais: 3.2. Lineārās programēšanas uzdevumu risināšanas grafiskā Augstāk: 3. LINEĀRĀS PROGRAMMĒŠANAS UZDEVUMI Iepriekšējais: 3. LINEĀRĀS PROGRAMMĒŠANAS UZDEVUMI