LINEARNO PROGRAMIRANJE: ZA KAJ GRE, MODELI, OMEJITVE, APLIKACIJE - MATEMATIKA - 2025

Linearno programiranje je matematična metoda, ki se uporablja za optimizacijo (povečati ali zmanjšati kot je primerno) funkcija S spremenljivke so omejene, tako dolgo, kot funkcija in omejitve so linearno odvisne spremenljivke.

Na splošno funkcija za optimizacijo modelira praktične razmere, kot je dobiček proizvajalca, katerega vložki, delovna sila ali stroji so omejeni.

Slika 1. Linearno programiranje se pogosto uporablja za optimizacijo dobička. Vir: Piqsels.

Eden najpreprostejših primerov je linearna funkcija, ki jo je treba maksimizirati, kar je odvisno le od dveh spremenljivk, imenovanih spremenljivke odločitve. Lahko je v obliki:

Z = k ₁ x + k ₂ y

S konstanto k ₁ in k ₂ . Ta funkcija je znana kot ciljna funkcija. Seveda obstajajo situacije, ki za študij zaslužijo več kot dve spremenljivki, ki so bolj zapletene:

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

In omejitve so tudi matematično modelirane s sistemom enačb ali neenakosti, enako linearnih v x in y.

Nabor rešitev v tem sistemu se imenuje izvedljive rešitve ali izvedljive točke. In med izvedljivimi točkami je vsaj ena, ki optimizira ciljno funkcijo.

Linearno programiranje sta neodvisno razvila ameriški fizik in matematik George Dantzig (1914-2005) in ruski matematik in ekonomist Leonid Kantorovich (1912-1986) kmalu po drugi svetovni vojni.

Metoda reševanja problemov, znana kot simplex metoda, je zamisel Dantziga, ki je delal za ameriške zračne sile, univerzo Berkeley in univerzo Stanford.

Slika 2. Matematika George Dantzig (levo) in Leonid Kantorovich (desno). Vir: F. Zapata.

Modeli linearnega programiranja

Za vzpostavitev modela linearnega programiranja, ki je primeren za praktične razmere, so potrebni naslednji elementi:

-Objektivna funkcija

-Spremenljivke natančnosti

- Omejitve

V ciljni funkciji določite, kaj želite doseči. Recimo, na primer, da želite povečati dobiček iz proizvodnje nekaterih izdelkov. Nato se vzpostavi funkcija "dobiček", glede na ceno, po kateri se izdelki prodajo.

V matematičnem smislu je to funkcijo mogoče izraziti okrajšano s pomočjo seštevanja:

Z = ∑k _i x _i

V tej enačbi so k _i koeficienti, x _i pa odločilne spremenljivke.

Spremenljivke odločitve so elementi sistema, katerega nadzor je bil in njihove vrednosti so pozitivne realne številke. V predlaganem primeru so spremenljivke odločitve količina vsakega izdelka, ki ga je treba izdelati, da se doseže največji dobiček.

Nazadnje imamo omejitve, ki so linearne enačbe ali neenakosti glede na spremenljive odločitve. Opisujejo omejitve problema, ki so znane in so lahko na primer količine surovin, ki so na voljo pri izdelavi.

Vrste omejitev

Omejitve lahko imate v številu M, začenši od j = 1 do j = M. Matematično so omejitve treh vrst:

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

Prva omejitev je tipa linearne enačbe in pomeni, da je treba spoštovati vrednost A _j , ki je znana.

Dve preostali omejitvi sta linearni neenakosti, kar pomeni, da je mogoče upoštevati ali preseči znane vrednosti B _j in C _j , kadar je simbol, ki se pojavi, ≥ (večji ali enak) ali spoštovan ali ne presežen, če je simbol ≤ (manjše ali enako).

Primer modela

Področja uporabe so zelo raznolika, od poslovne administracije do prehrane, toda za razumevanje metode je spodaj predlagan preprost model praktične situacije z dvema spremenljivkama.

Lokalna slaščičarna je znana po dveh specialitetah: črna gozdna torta in žrtvena torta.

Pri njegovi pripravi potrebujejo jajca in sladkor. Za črni gozd potrebujete 9 jajc in 500 g sladkorja, za žrtvenik pa 8 jajc in 800 g sladkorja. Zadevne prodajne cene znašajo 8 do 10 USD.

Težava je: Koliko kolačkov vsake vrste mora pekarna narediti, da poveča svoj dobiček, saj ve, da ima 10 kilogramov sladkorja in 144 jajc?

Spremenljivke odločitve

Spremenljivke odločitve so "x" in "y", ki prevzamejo resnične vrednosti:

-x: število črnih gozdnih pogač

-y: torte žrtvovalnega tipa

Omejitve

Omejitve so podane s tem, da je število pogač pozitivna količina in da je za njihovo pripravo omejenih količin surovin.

Zato so v matematični obliki te omejitve v obliki:

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

Omejitve 1 in 2 predstavljata pogoj neaktivnosti, ki je bil predhodno izpostavljen, vse postavljene neenakosti pa so linearne. V omejitvah 3 in 4 so vrednosti, ki jih ne smete presegati: 144 jajc in 10 kg sladkorja.

Ciljna funkcija

Končno je ciljna funkcija dobiček, ki ga dobimo pri izdelavi "x" količine črnih gozdnih pogač plus "y" količine žrtvinic. Zgradi se tako, da ceno pomnoži s količino izdelanih tort in doda se za vsako vrsto. To je linearna funkcija, ki jo imenujemo G (x, y):

G = 8x + 10y

Metode reševanja

Različne metodologije rešitev vključujejo grafične metode, algoritem simpleksa in metodo notranje točke, če jih naštejemo le nekaj.

- Grafična ali geometrijska metoda

Če imate težavo z dvema spremenljivkama, kot je ta v prejšnjem razdelku, omejitve določajo mnogokotno območje v ravnini xy, ki se imenuje izvedljivo območje ali območje preživetja.

Slika 3. Izvedljivo območje, kjer je rešitev optimizacijskega problema. Vir: Wikimedia Commons.

To območje je zgrajeno z omejitvenimi črtami, ki so črte, dobljene iz neenakosti omejitev in delujejo samo z znakom enakosti.

V primeru pekarne, ki želi optimizirati dobiček, so omejitve naslednje:

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

Vse točke v regiji, omejene s temi črtami, so možne rešitve, zato jih je neskončno veliko. Razen v primeru, ko se izkaže, da je izvedljivo območje prazno, v tem primeru postavljena težava nima rešitve.

Na srečo, za težavo s pecivom izvedljiva regija ni prazna, spodaj jo imamo.

Slika 4. Izvedljivo področje problema s pecivom. Vrstica z dobitkom 0 prečka izvor. Vir: F. Zapata z Geogebra.

Optimalno rešitev, če obstaja, poiščemo s pomočjo objektivne funkcije. Na primer, ko poskušamo najti največji dobiček G, imamo naslednjo vrstico, ki jo imenujemo izoprofitna vrstica:

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

S to vrstico dobimo vse pare (x, y), ki zagotavljajo dani dobitek G, zato obstaja družina črt glede na vrednost G, vendar vse z enakim naklonom -k ₁ / k ₂ , tako da so vzporedne črte.

Optimalna rešitev

Zdaj je mogoče pokazati, da je optimalna rešitev linearnega problema vedno skrajna točka ali meja izvedljive regije. Torej:

Če ima črta, ki je najbližje izvoru, ima celoten segment, ki je skupni z izvedljivim območjem, potem obstaja neskončno rešitev. Do tega primera pride, če je naklon črte izoprofita enak tistemu od drugih vrstic, ki omejujejo regijo.

Za naše pecivo so kandidatne točke A, B in C.

- Dantzigova simpleks metoda

Grafična ali geometrijska metoda je uporabna za dve spremenljivki. Vendar je bolj zapleteno, če obstajajo tri spremenljivke, in ga ni mogoče uporabiti za večje število spremenljivk.

Pri reševanju težav z več kot dvema spremenljivkama se uporablja metoda simpleksa, ki je sestavljena iz niza algoritmov za optimizacijo ciljnih funkcij. Za izvedbo izračunov se pogosto uporabljajo matrike in preprosta aritmetika.

Simplex metoda se začne z izbiro izvedljive rešitve in preverjanjem, ali je optimalna. Če je, smo težavo že rešili, če pa ni, nadaljujemo proti rešitvi, ki je bližja optimizaciji. Če rešitev obstaja, algoritem najde v nekaj poskusih.

Prijave

Linearno in nelinearno programiranje se uporablja na številnih področjih za sprejemanje najboljših odločitev v smislu zmanjšanja stroškov in povečanja dobička, ki niso vedno denarni, saj jih je mogoče meriti v času, na primer, če želite zmanjšati čas, ki je potreben izvesti vrsto operacij.

Tu je nekaj polj:

-V trženju se uporablja za iskanje najboljše kombinacije medijev (družbena omrežja, televizija, tisk in drugi) za oglaševanje določenega izdelka.

-Za dodelitev ustreznih nalog osebju podjetja ali tovarne ali razporedu le-teh.

- Pri izbiri najbolj hranljive hrane in z najnižjimi stroški v živinoreji in perutnini.

Rešene vaje

- Vaja 1

Grafično rešite model linearnega programiranja, ki je bil povzet v prejšnjih razdelkih.

Rešitev

Grafirati je treba nabor vrednosti, ki ga določa sistem omejitev, določen v težavi:

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

Območje, ki ga dobita neenakosti 1 in 2, ustreza prvemu kvadrantu kartezijanske ravnine. Glede neenakosti 3 in 4 začnemo z iskanjem omejitvenih vrstic:

9x + 8y = 144

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

Izvedljivo območje je štirikotnik, katerega opornice so točke A, B, C in D.

Najmanjši dobiček je 0, zato je vrstica 8x + 10y = 0 spodnja meja, izoprofitne vrstice pa nagib -8/10 = - 0,8.

Ta vrednost se razlikuje od pobočij drugih omejitvenih linij, in ker je izvedljivo območje omejeno, obstaja edinstvena rešitev.

Slika 5. Grafična rešitev vaje 1, ki prikazuje izvedljivo območje in raztopinsko točko C v eni od opornic omenjenega območja. Vir: F. Zapata.

Ta rešitev ustreza premici -0,8, ki poteka skozi katero koli točko A, B ali C, katere koordinate so:

A (11; 5.625)

B (0; 12,5)

C (16, 0)

Optimalna rešitev

Za vsako od teh točk izračunamo vrednost G:

- (11; 5.625): G _A = 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

Največji dobiček imajo proizvodnja 11 črnih gozdnih pogač in 5.625 kurbantinskih tort. Ta rešitev ustreza tisti, ki jo najdete v programski opremi.

- Vaja 2

Rezultat prejšnje vaje preverite s pomočjo funkcije Solver, ki je na voljo v večini preglednic, kot sta Excel ali LibreOffice Calc, ki vključujejo algoritem Simplex za optimizacijo v linearnem programiranju.

Rešitev

Slika 6. Podrobnosti rešitve iz vaje 1 v preglednici Libre Office Calc. Vir: F. Zapata.

Slika 7. Podrobnosti rešitve iz vaje 1 prek preglednice Libre Office Calc. Vir: F. Zapata.

Reference

1. Briljantno. Linearno programiranje. Pridobljeno: bril.org.
2. Eppen, G. 2000. Operacijske raziskave v upravni znanosti. 5. Izdaja. Dvorana Prentice.
3. Haeussler, E. 1992. Matematika za management in ekonomijo. 2. Izdaja. Grupo Uredništvo Iberoamericana.
4. Hiru.eus. Linearno programiranje. Pridobljeno: hiru.eus.
5. Wikipedija. Linearno programiranje. Pridobljeno: es. wikipedia.org.