LINIJINIS PROGRAMAVIMAS: KAM JIS SKIRTAS, MODELIAI, APRIBOJIMAI, PROGRAMOS - MATEMATIKA - 2025

Tiesinis programavimas yra matematinis metodas, kuris yra naudojamas siekiant optimizuoti (padidinti arba sumažinti, kaip tinkama) funkcijos, kurių kintamieji yra apribotas, taip ilgai, kaip funkcija ir apribojimai yra tiesiškai priklausomi kintamieji.

Paprastai optimizuojama funkcija modeliuoja praktinę situaciją, pavyzdžiui, gamintojo, kurio sąnaudos, darbo jėga ar mašinos yra ribotos, pelną.

1 paveikslas. Pelno optimizavimui plačiai naudojamas linijinis programavimas. Šaltinis: Piqsels.

Vienas iš paprasčiausių atvejų yra maksimali linijinė funkcija, kuri priklauso tik nuo dviejų kintamųjų, vadinamų sprendimo kintamaisiais. Tai gali būti tokios formos:

Z = k ₁ x + k ₂ y

Kai k ₁ ir k _{2 yra} pastovios. Ši funkcija vadinama objektyvia funkcija. Žinoma, yra situacijų, kurioms įvertinti reikia daugiau nei dviejų kintamųjų, nes jos yra sudėtingesnės:

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

Apribojimai taip pat matematiškai modeliuojami lygčių ar nelygybių sistema, vienodai tiesėmis x ir y.

Sprendimų rinkinys šioje sistemoje yra vadinamas įgyvendinamais sprendimais arba įmanomais taškais. Tarp galimų taškų yra bent vienas, optimizuojantis tikslo funkciją.

Linijinį programavimą savarankiškai sukūrė amerikiečių fizikas ir matematikas George'as Dantzigas (1914-2005) ir rusų matematikas bei ekonomistas Leonidas Kantorovičius (1912-1986) netrukus po Antrojo pasaulinio karo.

Problemų sprendimo metodas, žinomas kaip simplekso metodas, yra Dantzigo, dirbusio JAV oro pajėgose, Berklio universitete ir Stanfordo universitete, smegenys.

2 pav. Matematikai George'as Dantzigas (kairėje) ir Leonidas Kantorovičius (dešinėje). Šaltinis: F. Zapata.

Linijiniai programavimo modeliai

Elementai, reikalingi sukurti linijinį programavimo modelį, tinkantį praktinei situacijai, yra šie:

-Objektyvi funkcija

-Pasprendimo kintamieji

- Apribojimai

Tikslo funkcijoje jūs apibrėžiate, ko norite pasiekti. Pavyzdžiui, tarkime, kad norite padidinti pelną, gautą gaminant tam tikrus produktus. Tada nustatoma „pelno“ funkcija, atsižvelgiant į kainą, kuria parduodami produktai.

Matematiškai šią funkciją galima išreikšti sutrumpintai, naudojant sumavimo žymėjimą:

Z = ∑k _i x _i

Šioje lygtyje k _i yra koeficientai, o x _i yra sprendimo kintamieji.

Sprendimo kintamieji yra sistemos elementai, kuriuos valdė, o jų vertės yra teigiami tikrieji skaičiai. Siūlomame pavyzdyje sprendimo kintamieji yra kiekvieno gaminamo produkto kiekis, norint gauti maksimalų pelną.

Galiausiai turime apribojimus, kurie yra tiesinės lygtys arba nelygybės sprendimo kintamųjų atžvilgiu. Jie apibūdina žinomus problemos apribojimus, kurie gali būti, pavyzdžiui, gamyboje naudojamų žaliavų kiekiai.

Apribojimų rūšys

Galite turėti keletą M apribojimų, pradedant nuo j = 1 iki j = M. Matematiškai yra trijų rūšių apribojimai:

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

Pirmasis apribojimas yra tiesinės lygties tipo ir reiškia, kad turi būti laikomasi žinomos A _j vertės .

Du likę apribojimai yra tiesinė nelygybė ir tai reiškia, kad žinomų reikšmių B _j ir C _j gali būti laikomasi arba viršyta, kai pasirodo simbolis ≥ (didesnis arba lygus) arba jo laikomasi ar jo neviršijama, jei simbolis ≤ (mažesnis arba lygus).

Modelio pavyzdys

Taikymo sritys yra labai įvairios, pradedant verslo administravimu ir baigiant mityba, tačiau norint suprasti šį metodą, toliau pateikiamas paprastas praktinės situacijos modelis su dviem kintamaisiais.

Vietos konditerija yra žinoma dėl dviejų patiekalų: juodojo miško pyrago ir sacripantino pyrago.

Jai ruošti reikia kiaušinių ir cukraus. Juodojo miško jums reikia 9 kiaušinių ir 500 g cukraus, o sakripantino - 8 kiaušinių ir 800 g cukraus. Atitinkamos pardavimo kainos yra 8 USD ir 10 USD.

Problema yra tokia: kiek kiekvienos rūšies pyragaičių turi būti pagaminta iš kepyklos, kad būtų galima padidinti pelną, žinant, kad joje yra 10 kilogramų cukraus ir 144 kiaušiniai?

Sprendimo kintamieji

Sprendimo kintamieji yra „x“ ir „y“, kurie imasi realiųjų verčių:

-x: juodųjų miško pyragų skaičius

-y: sacripantine tipo pyragai.

Apribojimai

Apribojimus lemia tai, kad tortų skaičius yra teigiamas, o jų paruošimui yra ribotas kiekis žaliavų.

Todėl matematiškai šie apribojimai yra tokie:

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

1 ir 2 apribojimai sudaro prieš tai buvusio negatyvo sąlygą, o visos iškeltos nelygybės yra tiesinės. 3 ir 4 apribojimai yra vertės, kurių negalima viršyti: 144 kiaušiniai ir 10 kg cukraus.

Objektyvi funkcija

Galiausiai tikslinė funkcija yra pelnas, gautas gaminant „x“ kiekį juodųjų miško pyragų ir „y“ kiekį sacripantinų. Jis pastatytas padauginus kainą iš pagamintų pyragų kiekio ir pridedant kiekvieną rūšį. Tai linijinė funkcija, kurią mes vadinsime G (x, y):

G = 8x + 10y

Sprendimo metodai

Įvairios sprendimo metodikos apima keletą grafinių metodų, simplekso algoritmą ir vidinio taško metodą.

- Grafinis ar geometrinis metodas

Kai turite dviejų kintamųjų problemą, tokią, kokia yra ankstesniame skyriuje, apribojimai nustato daugiakampę sritį xy plokštumoje, vadinamą įmanomą sritį arba gyvybingumo sritį.

3 pav. Galimas regionas, kuriame rastas optimizacijos problemos sprendimas. Šaltinis: „Wikimedia Commons“.

Šis regionas sukonstruotas naudojant apribojimų linijas, kurios yra linijos, gautos iš apribojimų nelygybės, veikiančios tik lygybės ženklu.

Kepyklos, norinčios padidinti pelną, atveju:

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

Visi taškai regione, kuriuos riboja šios linijos, yra įmanomi sprendimai, todėl jų yra be galo daug. Išskyrus atvejus, kai įmanomas regionas atrodo tuščias, tokiu atveju iškilusi problema neturi sprendimo.

Laimei, konditerijos problemos įgyvendinamas regionas nėra tuščias, jį turime žemiau.

4 pav. Galimas konditerijos problemos regionas. Linija su prieaugiu 0 kerta kilmę. Šaltinis: F. Zapata su „Geogebra“.

Optimalus sprendimas, jei jis egzistuoja, randamas pasitelkiant tikslo funkciją. Pvz., Bandant rasti didžiausią pelną G, turime šią eilutę, kuri vadinama „iso-profit line“:

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

Su šia linija gauname visas poras (x, y), kurios suteikia nurodytą padidėjimą G, taigi yra linijų šeima pagal G vertę, tačiau visos turi tą patį nuolydį -k ₁ / k ₂ , taigi jos yra lygiagrečios linijos.

Optimalus sprendimas

Dabar galima parodyti, kad optimalus linijinės problemos sprendimas visada yra galimas regiono kraštinis taškas arba viršūnė. Taigi:

Jei linija, esanti arčiausiai kilmės, turi visą segmentą, bendrą su įmanomu regionu, sakoma, kad sprendimų yra begalė. Šis atvejis įvyksta, jei izolioto pelno linijos nuolydis yra lygus bet kurios kitos tiesės, ribojančios regioną, nuolydžiui.

Konditerijos gaminių viršūnės yra A, B ir C.

- Dantzigo simplex metodas

Grafinis arba geometrinis metodas taikomas dviem kintamiesiems. Tačiau sudėtingiau, kai yra trys kintamieji, ir neįmanoma jų naudoti didesniam kintamųjų skaičiui.

Sprendžiant problemas, susijusias su daugiau nei dviem kintamaisiais, naudojamas simplekso metodas, kurį sudaro daugybė algoritmų, siekiant optimizuoti tikslo funkcijas. Skaičiavimams dažnai naudojamos matricos ir paprasta aritmetika.

Paprastasis metodas prasideda pasirenkant galimą sprendimą ir patikrinant, ar jis yra optimalus. Jei taip yra, mes jau išsprendėme problemą, bet jei jos nėra, toliau ieškome sprendimo, artimesnio optimizavimui. Jei sprendimas egzistuoja, algoritmas jį suranda per kelis bandymus.

Programos

Linijinis ir netiesinis programavimas yra taikomas daugelyje sričių, siekiant priimti geriausius sprendimus, susijusius su išlaidų mažinimu ir pelno didinimu, kurie ne visada yra pinigai, nes jie gali būti matuojami laike, pavyzdžiui, jei norite sumažinti reikiamą laiką. atlikti daugybę operacijų.

Čia yra keli laukai:

-Rinkodaroje jis naudojamas norint rasti geriausią žiniasklaidos priemonių (socialinių tinklų, televizijos, spaudos ir kitų) derinį tam tikram produktui reklamuoti.

-Paskirtus tinkamas užduotis įmonės ar gamyklos personalui ar jiems numatytus grafikus.

-Renkantis maistingiausią maistą ir kuo mažesnėmis sąnaudomis gyvulininkystės ir paukštininkystės pramonėje.

Išspręsta mankšta

- 1 pratimas

Grafiškai išspręskite ankstesniuose skyriuose iškeltą linijinio programavimo modelį.

Sprendimas

Būtina nubraižyti reikšmių rinkinį, kurį nustato problemoje nurodyta apribojimų sistema:

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

Regionas, kurį nurodo 1 ir 2 nelygybės, atitinka pirmąjį Dekarto plokštumos kvadrantą. Kalbant apie 3 ir 4 nelygybę, pirmiausia reikia surasti apribojimų linijas:

9x + 8y = 144

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

Galimas regionas yra keturkampis, kurio viršūnės yra taškai A, B, C ir D.

Mažiausias pelnas yra 0, todėl linija 8x + 10y = 0 yra apatinė riba, o izoliuojamo pelno linijų nuolydis –8/10 = - 0,8.

Ši vertė skiriasi nuo kitų ribojimo linijų nuolydžių ir kadangi galimas regionas yra ribojamas, egzistuoja unikalus sprendimas.

1 paveikslas. Grafinis 1 pratimo sprendimas, parodantis įmanomą sritį ir sprendimo tašką C vienoje iš minėtos srities viršūnių. Šaltinis: F. Zapata.

Šis sprendimas atitinka nuolydžio liniją -0,8, einančią per bet kurį tašką A, B ar C, kurio koordinatės:

A (11; 5.625)

B (0; 12,5)

C (16,0)

Optimalus sprendimas

Mes apskaičiuojame G reikšmę kiekvienam iš šių taškų:

- (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

Didžiausias pelnas gaunamas gaminant 11 juodųjų miško pyragų ir 5 625 sakripantinių pyragų. Šis sprendimas sutinka su tuo, kuris rastas naudojant programinę įrangą.

- 2 pratimas

Patikrinkite ankstesnio pratimo rezultatą naudodamiesi funkcija „Solver“, pasiekiama daugelyje skaičiuoklių, tokių kaip „Excel“ ar „LibreOffice Calc“, kuriose integruotas „Simplex“ algoritmas, skirtas optimizuoti linijinį programavimą.

Sprendimas

6 pav. Išsami informacija apie 1 pratimą per „Libre Office Calc“ skaičiuoklę. Šaltinis: F. Zapata.

7 pav. Išsami informacija apie 1 pratimą per „Libre Office Calc“ skaičiuoklę. Šaltinis: F. Zapata.

Nuorodos

1. Nuostabus. Linijinis programavimas. Atkurta iš: brilliant.org.
2. Eppen, G. 2000. Administracinių mokslų operacijų tyrimai. 5-asis. Leidimas. Prentice salė.
3. Haeussler, E. 1992. Vadybos ir ekonomikos matematika. 2-asis. Leidimas. „Grupo“ redakcija „Iberoamericana“.
4. Hiru.eus. Linijinis programavimas. Atkurta iš: hiru.eus.
5. Vikipedija. Linijinis programavimas. Išieškota iš: es. wikipedia.org.