LINEĀRĀ PROGRAMMĒŠANA: KAM TĀ PAREDZĒTA, MODEĻI, IEROBEŽOJUMI, LIETOJUMPROGRAMMAS - MATEMĀTIKA - 2025

Lineārā programmēšana ir matemātiska metode, kas tiek izmantota, lai optimizētu (palielināt vai samazināt pēc vajadzības) funkciju, kura mainīgie ir ierobežota, jo kamēr funkcija un ierobežojumi ir lineāri atkarīgie mainīgie lielumi.

Parasti optimizējamā funkcija modelē praktisko situāciju, piemēram, tāda ražotāja peļņu, kura ieguldītie resursi, darbaspēks vai mašīnas ir ierobežotas.

1. attēls. Lai optimizētu peļņu, plaši tiek izmantota lineārā programmēšana. Avots: Piqsels.

Viens no vienkāršākajiem gadījumiem ir maksimāla lineārā funkcija, kas ir atkarīga tikai no diviem mainīgajiem, ko sauc par lēmumu mainīgajiem. Tam var būt šāda forma:

Z = k ₁ x + k ₂ g

Ar k ₁ un k ₂ konstanti. Šo funkciju sauc par objektīvo funkciju. Protams, ir situācijas, kuru izpētei ir vajadzīgi vairāk nekā divi mainīgie lielumi:

Z = k ₁ x ₁ + k ₂ x ₂ + k ₃ x ₃ +….

Arī ierobežojumus matemātiski modelē vienādojumu vai nevienādību sistēma, vienādi lineāra x un y.

Risinājumu kopumu šajā sistēmā sauc par iespējamiem risinājumiem vai iespējamiem punktiem. Starp iespējamiem punktiem ir vismaz viens, kas optimizē objekta funkciju.

Lineāro programmēšanu patstāvīgi izstrādāja amerikāņu fiziķis un matemātiķis Džordžs Dantzigs (1914-2005) un krievu matemātiķis un ekonomists Leonīds Kantorovičs (1912–1986) neilgi pēc Otrā pasaules kara.

Problēmu risināšanas metode, kas pazīstama kā vienkāršā metode, ir Dantzig, kurš strādāja ASV Gaisa spēkos, Bērklija universitātē un Stenfordas universitātē, prāta bērni.

2. attēls. Matemātiķi Džordžs Dantigs (pa kreisi) un Leonīds Kantorovičs (pa labi). Avots: F. Zapata.

Lineārās programmēšanas modeļi

Elementi, kas nepieciešami, lai izveidotu lineāru programmēšanas modeli, kas piemērots praktiskai situācijai, ir:

-Objektīvā funkcija

-Izlēmuma mainīgie

-Ierobežojumi

Mērķa funkcijā jūs definējat, ko vēlaties sasniegt. Piemēram, pieņemsim, ka vēlaties maksimizēt peļņu no noteiktu produktu ražošanas. Tad tiek noteikta funkcija "peļņa" atkarībā no cenas, par kādu produkti tiek pārdoti.

Matemātiski šo funkciju var izteikt saīsināti, izmantojot summējošo notāciju:

Z = ∑k _i x _i

Šajā vienādojumā k _i ir koeficienti un x _i ir lēmuma mainīgie.

Lēmuma mainīgie ir sistēmas elementi, kurus kontrolēja, un to vērtības ir pozitīvi reālie skaitļi. Piedāvātajā piemērā lēmuma mainīgie ir katra saražotā produkta daudzums, lai iegūtu maksimālu peļņu.

Visbeidzot, mums ir ierobežojumi, kas ir lineāri vienādojumi vai nevienlīdzība lēmumu mainīgo izteiksmē. Tie apraksta zināmos problēmas ierobežojumus, kas var būt, piemēram, ražošanā pieejamo izejvielu daudzumi.

Ierobežojumu veidi

Jums var būt vairāki ierobežojumi M, sākot no j = 1 līdz j = M. Matemātiski ierobežojumi ir trīs veidi:

1. A _j = ∑ a _ij . x _i
2. B _j ≥ ∑ b _ij . x _i
3. C _j ≤ ∑ c _ij . x _i

Pirmais ierobežojums ir lineārā vienādojuma tips un nozīmē, ka ir jāievēro zināmā vērtība A _j .

Divi atlikušie ierobežojumi ir lineāras nevienādības, un tas nozīmē, ka zināmās vērtības B _j un C _j var ievērot vai pārsniegt, ja parādītais simbols ir ≥ (lielāks vai vienāds ar) vai tiek ievērots vai nepārsniegts, ja simbols ir ≤ (mazāks vai vienāds ar).

Modeļa piemērs

Pielietojuma jomas ir ļoti dažādas, sākot no biznesa administrēšanas un beidzot ar uzturu, taču, lai saprastu metodi, turpmāk tiek piedāvāts vienkāršs praktiskas situācijas modelis ar diviem mainīgiem.

Vietējā konditoreja ir pazīstama ar diviem ēdieniem: melnā meža kūka un sakripantīna kūka.

Sagatavošanā viņiem ir vajadzīgas olas un cukurs. Melnajam mežam jums vajadzīgas 9 olas un 500 g cukura, bet sacripantīnam - 8 olas un 800 g cukura. Attiecīgās pārdošanas cenas ir USD 8 un USD 10.

Problēma ir šāda: cik daudz kūku katra veida maiznīcai jāgatavo, lai palielinātu savu peļņu, zinot, ka tajā ir 10 kilogrami cukura un 144 olas?

Lēmuma mainīgie

Lēmuma mainīgie ir "x" un "y", kuriem ir reālās vērtības:

-x: melnā meža kūku skaits

-y: sacripantine tipa kūkas.

Ierobežojumi

Ierobežojumus piešķir tas, ka kūku skaits ir pozitīvs, un to pagatavošanai ir ierobežots izejvielu daudzums.

Tāpēc matemātiskā formā šie ierobežojumi izpaužas šādi:

1. x ≥ 0
2. un ≥0
3. 9x + 8y ≤ 144
4. 0,5 x + 0,8 y ≤ 10

1. un 2. ierobežojums ir iepriekš pakļautā nenegativitātes nosacījums, un visas izvirzītās nevienlīdzības ir lineāras. 3. un 4. ierobežojumā ir vērtības, kuras nedrīkst pārsniegt: 144 olas un 10 kg cukura.

Mērķa funkcija

Visbeidzot, mērķa funkcija ir peļņa, kas iegūta, ražojot melnā meža kūku “x” daudzumu plus sacripantīnu “y” daudzumu. To veido, reizinot cenu ar izgatavoto kūku daudzumu un pievienojot katram veidam. Tā ir lineāra funkcija, kuru mēs sauksim G (x, y):

G = 8x + 10y

Risināšanas metodes

Dažādās risinājumu metodoloģijās ietilpst grafiskās metodes, simpleksa algoritms un interjera punkta metode, lai nosauktu dažus.

- grafiskā vai ģeometriskā metode

Ja rodas tāda divu mainīgo problēma kā iepriekšējā sadaļā, ierobežojumi nosaka daudzstūru reģionu xy plaknē, ko sauc par iespējamo reģionu vai dzīvotspējas reģionu.

3. attēls. Iespējamais reģions, kurā ir atrasts optimizācijas problēmas risinājums. Avots: Wikimedia Commons.

Šis reģions tiek veidots, izmantojot ierobežojuma līnijas, kas ir līnijas, kas iegūtas no ierobežojumu nevienlīdzības, strādājot tikai ar vienlīdzības zīmi.

Maizes ceptuvei, kas vēlas optimizēt peļņu, ierobežojumi ir šādi:

1. x = 0
2. y = 0
3. 9x + 8y = 144
4. 0,5 x + 0,8 y = 10

Visi reģioni, kurus ierobežo šīs līnijas, ir iespējami risinājumi, tāpēc to ir bezgalīgi daudz. Izņemot gadījumus, kad iespējamais reģions izrādās tukšs, šajā gadījumā uzdotajai problēmai nav risinājuma.

Par laimi, konditorejas izstrādājumu problēmai iespējamais reģions nav tukšs, mums tas ir norādīts zemāk.

4. attēls. Iespējamais konditorejas problēmas reģions. Līnija ar palielinājumu 0 šķērso izcelsmi. Avots: F. Zapata ar Geogebra.

Optimālais risinājums, ja tāds pastāv, tiek atrasts ar mērķa funkcijas palīdzību. Piemēram, mēģinot atrast maksimālo peļņu G, mums ir šāda rinda, ko sauc par izpeļņas līniju:

G = k ₁ x + k ₂ y → y = -k ₁ x / k ₂ + G / k ₂

Ar šo līniju iegūstam visus pārus (x, y), kas nodrošina doto pieaugumu G, tāpēc ir līniju saime atbilstoši G vērtībai, bet visām ar vienādu slīpumu -k ₁ / k ₂ , tātad paralēlas līnijas.

Optimālais risinājums

Tagad var parādīt, ka optimāls lineāras problēmas risinājums vienmēr ir iespējamā reģiona galējais punkts vai virsotne. Tātad:

Ja līnijai, kas ir vistuvāk izcelsmei, ir viss kopīgais segments ar iespējamo reģionu, tiek teikts, ka ir bezgalīgi risinājumi. Šis gadījums notiek, ja izlejošās peļņas līnijas slīpums ir vienāds ar jebkuras citas līnijas, kas ierobežo šo reģionu, slīpumu.

Mūsu konditorejai kandidātu virsotnes ir A, B un C.

- Dancigas simpleksa metode

Grafiskā vai ģeometriskā metode ir piemērojama diviem mainīgajiem. Tomēr tas ir sarežģītāk, ja ir trīs mainīgie, un nav iespējams izmantot lielākam mainīgo skaitam.

Risinot problēmas ar vairāk nekā diviem mainīgajiem, tiek izmantota simpleksa metode, kas sastāv no algoritmu sērijas, lai optimizētu objekta funkcijas. Aprēķinu veikšanai bieži izmanto matricas un vienkāršu aritmētiku.

Vienkāršā metode sākas, izvēloties iespējamu risinājumu un pārbaudot, vai tas ir optimāls. Ja tā ir, mēs problēmu jau esam atrisinājuši, bet, ja tā nav, mēs turpinām meklēt risinājumu, kas tuvāk optimizācijai. Ja risinājums pastāv, algoritms to atrod dažos mēģinājumos.

Lietojumprogrammas

Lineārā un nelineārā programmēšana tiek izmantota daudzās jomās, lai pieņemtu labākos lēmumus izmaksu samazināšanas un peļņas palielināšanas ziņā, kas ne vienmēr ir monetāri, jo tos var izmērīt laikā, piemēram, ja vēlaties samazināt nepieciešamo laiku. veikt virkni operāciju.

Šeit ir daži lauki:

-Mārketingā to izmanto, lai atrastu labāko mediju (sociālo tīklu, televīzijas, preses un citu) kombināciju, lai reklamētu noteiktu produktu.

-Piemērojot atbilstošus uzdevumus uzņēmuma vai rūpnīcas personālam vai grafikus viņiem.

-Atverot barojošāko pārtiku un ar viszemākajām izmaksām lopkopības un mājputnu nozarē.

Atrisināti vingrinājumi

- 1. vingrinājums

Grafiski atrisiniet iepriekšējās sadaļās izvirzīto lineārās programmēšanas modeli.

Risinājums

Ir nepieciešams grafiks vērtību kopumu, ko nosaka problēmā norādītā ierobežojumu sistēma:

1. x ≥ 0
2. un ≥0
3. 9x + 8y ≤ 144
4. 0,5 x + 0,8 y ≤ 10

Reģions, ko piešķir 1. un 2. nevienādība, atbilst Dekarta plaknes pirmajam kvadrantam. Attiecībā uz 3. un 4. nevienlīdzību mēs vispirms sākam atrast ierobežojuma līnijas:

9x + 8y = 144

0,5 x + 0,8y = 10 → 5x + 8y = 100

Iespējamais reģions ir četrstūris, kura virsotnes ir punkti A, B, C un D.

Minimālā peļņa ir 0, tāpēc līnija 8x + 10y = 0 ir apakšējā robeža, un izoli peļņas līniju slīpums ir -8/10 = - 0,8.

Šī vērtība atšķiras no citu ierobežojošo līniju slīpumiem, un, tā kā iespējamais reģions ir ierobežots, eksistē unikālais risinājums.

5. attēls. 1. vingrinājuma grafiskais risinājums, parādot iespējamo reģionu un risinājuma punktu C vienā no minētā reģiona virsotnēm. Avots: F. Zapata.

Šis risinājums atbilst slīpuma līnijai -0,8, kas iet caur jebkuru punktu A, B vai C, kura koordinātas ir:

A (11; 5.625)

B (0; 12,5)

C (16, 0)

Optimāls risinājums

Mēs aprēķinām G vērtību katram no šiem punktiem:

- (11; 5,625): G = 8 x 11 + 10 x 5,625 = 144,25

- (0; 12,5): G _B = 8 x 0 + 10 x 12,5 = 125

- (16, 0): G _C = 8 x 16 + 10 x 0 = 128

Vislielākā peļņa ir 11 melnā meža kūku un 5 625 sakripantīna kūku ražošanā. Šis risinājums atbilst risinājumam, kas atrasts, izmantojot programmatūru.

- 2. vingrinājums

Pārbaudiet iepriekšējā uzdevuma rezultātu, izmantojot funkciju Solver, kas pieejama lielākajā daļā izklājlapu, piemēram, Excel vai LibreOffice Calc, kurās ir iekļauts vienkāršs algoritms optimizēšanai lineārajā programmēšanā.

Risinājums

6. attēls. Informācija par 1. vingrinājuma risinājumu, izmantojot Libre Office Calc izklājlapu. Avots: F. Zapata.

7. attēls. Informācija par 1. vingrinājuma risinājumu, izmantojot Libre Office Calc izklājlapu. Avots: F. Zapata.

Atsauces

1. Lieliski. Lineārā programmēšana. Atgūts no: brilliant.org.
2. Eppen, G. 2000. Operāciju izpēte administratīvajā zinātnē. 5. Izdevums. Prentice zāle.
3. Hausslers, E. 1992. Vadības un ekonomikas matemātika. 2. Izdevums. Grupo Editorial Iberoamericana.
4. Hiru.eus. Lineārā programmēšana. Atgūts no: hiru.eus.
5. Wikipedia. Lineārā programmēšana. Atgūts no: es. wikipedia.org.