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

3.3.3. Minimizācijas problēma

Ilustrēsim simpleksa metodes lietošanu vēl vienas problēmas atrisināšanai. Problēma:

$$F=x_{1}-2x_{2}\longrightarrow min,$$

$$x_{1}+x_{2}\geq 1,$$

$$x_{1}-x_{2}\geq - 2,$$

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

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

1. solis. Ieved papildmainīgos $x_{3}$, $x_{4}$, $x_{5}$, pārveidojot nevienādības vienādībās:

$$x_{1}+x_{2}=1+x_{3},\;\;x_{3}\geq 0,$$

$$x_{1}-x_{2}=-2+x_{4},\;\;x_{4}\geq 0,$$

$$4x_{1}+x_{2}+x_{5}=12,\;\;x_{5}\geq 0.$$

Modificētās problēmas dimensionalitāte $N = 5$ (pieci mainīgie), bet ierobežojumu skaits $m=3$.

2. solis. Aprēķināsim pirmās virsotnes koordinātas. Noteiksim skaitļus $x_{1}$, $x_{2}$, $x_{3}$, $x_{4}$ un $x_{5}$ tā, lai divi ($N-m=5-3=2$, problēmas dimensionalitātes un ierobežojumu skaita starpība) no tiem būtu vienādi ar nulli. Pārējo mainīgo vērtības tiks aprēķinātas, izmantojot ierobežojumus. Kombinācija $x_{1}=x_{2}=0$ neder, jo tad $1+x_{3}=0$, un $x_{3}$ ir negatīvs. Mēģinām citu kombināciju $x_{1}=x_{3}=0$. Nosakām $x_{2}$, $x_{4}$ un $x_{5}$ no ierobežojumiem un iegūstam vērtības:

$$x_{1}=0,\;\;x_{3}=0,\;\;x_{2}=1,\;\;x_{4}=1,\;\;x_{5}=11.$$

Visas vērtības ir nenegatīvas, tātad iegūstam pieļaujamu punktu. Punkts $(x_{1};x_{2})=(0;1)$ uz $(x_{1};x_{2})$-plaknes atbilst pieļaujamā apgabala virsotnei $A$ (skat. 3.7. zīm.). Tālāk, jāpārvietojas pa pieļaujamā apgabala robežu no virsotnes uz virsotni, uzlabojot mērķa funkcijas vērtības. Nav nozīmes, kura virsotne bija pirmā, ir svarīgi tikai, lai tā būtu pieļaujama (virsotne skaitās pieļaujama, ja skaitļi $x_{1}$ un $x_{2}$, kā arī no ierobežojumiem aprēķinātie skaitļi $x_{3}$, $x_{4}$ un $x_{5}$, būtu nenegatīvi).

3.7. zīm. 

3. solis. Ierobežojumu pārveidošana. Izdalīsim bāzes mainīgos un izteiksim ar tiem pārējos mainīgos. Par bāzes mainīgajiem izvēlamies vienādos ar nulli mainīgos $x_{1}$ un $x_{3}$. Pārējie mainīgie veido nebāzes mainīgo kopu. Nebāzes mainīgo skaits ir vienāds ar ierobežojumu skaitu, mūsu gadījuma ar $3$ ($m=3$), un tie ir $x_{2}$, $x_{4}$ un $x_{5}$. Izteiksim nebāzes mainīgos ar bāzes mainīgajiem:

$$x_{2}= \;1-x_{1}+x_{3},$$

$$x_{4} = \;x_{1}-x_{2}+2,$$

$$x_{5}= \;12-4x_{1}-x_{2},$$

jeb

$$x_{2}= \;1-x_{1}+x_{3},$$

$$x_{4} = \;x_{1}-(1-x_{1}+x_{3})+2,$$

$$x_{5}= \;12-4x_{1}-(1-x_{1}+x_{3}),$$

jeb

$$x_{2}= \;1-x_{1}+x_{3},$$ (3.23)

$$x_{4} = \;1+2x_{1}-x_{3},$$ (3.24)

$$x_{5}= \;11-3x_{1}-x_{3}.$$ (3.25)

Mērķa funkcija arī tiek izteikta ar bāzes mainīgajiem:

$$f=x_{1}-2x_{2}=x_{1}-2(1-x_{1}+x_{3})=-2+3x_{1}-2x_{3}\longrightarrow min.$$ (3.26)

4. solis. Jaunas virsotnes meklēšana. Tā kā tiek meklēts mērķa funkcijas minimums, mēģināsim uzlabot (samazināt) funkciju $f$, mainot vienu no bāzes mainīgajiem $x_{1}$ vai $x_{3}$. Aplūkosim abus variantus. Tā kā $x_{1}\geq 0$ un tekošā $x_{1}$ vērtība ir nulle, tad mainīt $x_{1}$ nevar, jo koeficients pie $x_{1}$ formulā (3.26) ir pozitīvs un tāpēc funkcijas $f$ vērtības var tikai pieaugt. Samazināt mērķa funkciju var mainot $x_{3}$. No nosacījuma (3.24) izriet, ka $x_{3}$ var palielināt tikai līdz $1$, jo pretējā gadījumā $x_{4}$ kļūs negatīvs. No nosacījuma (3.25) izriet, ka $x_{3}$ var palielināt tikai līdz $11$, jo pretējā gadījumā $x_{5}$ kļūs negatīvs. Izvēlamies mazāko vērtību $x_{3}=1$ un aprēķinām jaunās $x_{2}$, $x_{4}$ un $x_{5}$ vērtības. Jaunā punkta koordinātas:

$$x_{1}=0,\;\;x_{2}=2,\;\;x_{3}=1,\;\;x_{4}=0,\;\;x_{5}=10.$$

Punkts $(x_{1};x_{2})=(0;2)$ uz $(x_{1};x_{2})$-plaknes atbilst pieļaujamā apgabala virsotnei $B$.

5. solis. Cikla atkārtošana. Pēc ierobežojumu pārveidošanas mainīgais $x_{1}$ ir vienāds ar nulli, mainīgais $x_{4}$ kļuva par nulli, tātad divi ($N-m=2$) jaunie bāzes mainīgie ir $x_{1}$ un $x_{4}$. Jaunie trīs ($m=3$) nebāzes mainīgie ir $x_{2}$, $x_{3}$ un $x_{5}$. Izteiksim nebāzes mainīgos ar mainīgajiem. Izmantojot (3.24), atrodam

$$x_{3}=1+2x_{1}-x_{4}.$$ (3.27)

Izmantojot (3.23) un (3.27), iegūsim:

$$x_{2}=1-x_{1}+x_{3}=1-x_{1}+(1+2x_{1}-x_{4})$$

jeb

$$x_2=2+x_{1}-x_{4}.$$ (3.28)

Izmantojot (3.25) un (3.27), atrodam

$$x_5=11-3x_1-x_3=11-3x_1+(1+2x_1-x_4)$$

jeb

$$x_5=10-5x_{1}+x_{4}.$$ (3.29)

Mērķa funkcija arī tiek izteikta ar mainīgajiem $x_{1}$ un $x_{4}$:

$$f= \;-2+3x_{1}-2x_{3}$$

$$= \;-2+3x_{1}-2(1+2x_{1}-x_{4})$$

$$= \;-4-x_{1}+2x_{4}\longrightarrow min.$$

6. solis. Pāreja pie jauna punkta. Tā kā koeficients pie $x_{4}$ ir pozitīvs un $x_{4}\geq 0$, tad uzlabot (samazināt) mērķa funkciju var tikai palielinot $x_{1}$. No (3.29) izriet, ka $x_{1}$ var būt palielināts tikai līdz $2$, jo pretējā gadījumā $x_{5}$ kļūs negatīvs. Vienādībās (3.27) un (3.28) mainīgais $x_{1}$ ietilpst ar pozitīviem koeficientiem un tāpēc var būt palielināts līdz bezgalībai. Izvēlamies mazāko vērtību $x_{1}=2$, $x_{4}$ paliek nulle, bet $x_{2}$, $x_{3}$ un $x_{5}$ tiek aprēķināti pēc formulām (3.27), (3.28) un (3.29). Jaunā punkta koordinātas:

$$x_{1}=2,\;\;x_{2}=4,\;\;x_{3}=5,\;\;x_{4}=0,\;\;x_{5}=0.$$

Punkts $(x_{1};x_{2})=(2;4)$ uz $(x_{1};x_{2})$-plaknes atbilst pieļaujamā apgabala virsotnei $C$.

7. solis. Divi jaunie bāzes mainīgie: $x_{4}$ un $x_{5}$. Trīs jaunie nebāzes mainīgie: $x_{1}$, $x_{2}$ un $x_{3}$. Izteiksim nebāzes mainīgos ar bāzes mainīgajiem. Izmantojot formulas (3.27), (3.28) un (3.29), iegūstam:

$$x_1 = \;2+\frac{1}{3}x_{4}-\frac{1}{5}x_{5},$$

$$x_2 = \;2+x_{1}-x_{4}$$

$$= \;=2+\left(2+\frac{1}{5}x_{4}-\frac{1}{5}x_{5}\right)-x_{4}$$

$$= \;4-\frac{4}{5}x_{4}-\frac{1}{5}x_{5},$$

$$x_3= \;1+2x_{1}-x_{4}$$

$$= \;1+2\left(2+\frac{1}{5}x_{4}-\frac{1}{5}x_{5}\right)-x_{4}$$

$$= \;5-\frac{3}{5}x_{4}-\frac{2}{5}x_{5}.$$

Mērķa funkcija arī tiek izteikta ar nebāzes mainīgajiem $x_{3}$ un $x_{4}$:

$$f= \;-4-x_{1}+2x_{4}$$

$$= \;-4-\left(2+\frac{1}{5}x_{4}-\frac{1}{5}x_{5}\right)+2x_{4}$$

$$= \;-6+\frac{9}{5}x_{4}+\frac{1}{5}x_{5}\longrightarrow min.$$

8. solis. Tā kā koeficienti pie $x_{4}$ un $x_{5}$ ir pozitīvi, tad uzlabot (samazināt) mērķa funkciju vairs nav iespējams, mainot $x_{4}$ vai $x_{5}$. Secinājums: $f_{min}=-6$ punktā $(x_{1};x_{2})=(2;4)$.

3.1. piezīme. 

Simpleksa metodes aprakstu, analīzi, vēsturi un diskusijas par to var atrast grāmatā [1].

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