Ako trebate riješiti problem linearnog programiranja korištenjem simpleks tablica, onda će vam naša online usluga biti od velike pomoći. Simpleks metoda podrazumijeva sekvencijalno nabrajanje svih vrhova raspona prihvatljivih vrijednosti kako bi se pronašao vrh u kojem funkcija poprima ekstremnu vrijednost. U prvoj fazi se nađe neko rješenje koje se poboljšava u svakom sljedećem koraku. Takvo rješenje se naziva osnovnim. Evo slijeda radnji pri rješavanju problema linearnog programiranja korištenjem simpleks metode:
Prvi korak. U sastavljenoj tabeli, prije svega, trebate pogledati kolonu sa slobodnim članovima. Ako sadrži negativne elemente, onda je potrebno prijeći na drugi korak, ako ne, onda na peti.
Drugi korak. U drugom koraku potrebno je odlučiti koju varijablu isključiti iz baze, a koju uključiti kako bi se ponovo izračunala simpleks tablica. Da bismo to učinili, pogledamo kolonu sa slobodnim članovima i pronađemo negativni element u njemu. Linija s negativnim elementom naziva se vodećim. U njemu nalazimo maksimalni negativni element u apsolutnoj vrijednosti, stupac koji mu odgovara je sljedbenik. Ako postoje negativne vrijednosti među slobodnim članovima, ali ne u odgovarajućem redu, onda takva tablica neće imati rješenja. Varijabla u prvom redu, koja se nalazi u koloni slobodnih članova, isključena je iz baze, a varijabla koja odgovara vodećoj koloni je uključena u bazu.
Tabela 1.
| bazne varijable | Besplatni članovi u ograničenjima | Nebazične varijable | |||||
| x 1 | x2 | ... | x l | ... | x n | ||
| xn+1 | b 1 | a 11 | a 12 | ... | a 1l | ... | a 1n |
| xn+2 | b 2 | a 21 | a 22 | ... | a 2l | ... | a 2n |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| xn+r | b2 | a r1 | a r2 | ... | a rl | ... | a rn |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| xn+m | b m | a m1 | a m2 | ... | aml | ... | amn |
| F(x)max | F0 | -c 1 | -c 2 | ... | -c 1 | ... | -c n |
Treći korak. U trećem koraku ponovno izračunavamo cijelu simpleks tablicu pomoću posebnih formula, te formule se mogu vidjeti pomoću .
Četvrti korak. Ako nakon ponovnog izračunavanja u koloni slobodnih članova ostanu negativni elementi, idite na prvi korak, ako ih nema, idite na peti.
Peti korak. Ako ste došli do petog koraka, onda ste pronašli rješenje koje je prihvatljivo. Međutim, to ne znači da je optimalno. Biće optimalno samo ako su svi elementi u F-redu pozitivni. Ako to nije slučaj, onda je potrebno rješenje poboljšati, za šta nalazimo vodeći red i stupac za sljedeće preračunavanje prema sljedećem algoritmu. U početku nalazimo minimalni negativan broj u redu F, isključujući vrijednost funkcije. Kolona s ovim brojem će biti vodeća. Da bismo pronašli vodeći red, nalazimo omjer odgovarajućeg slobodnog člana i elementa iz vodeće kolone, pod uvjetom da su pozitivni. Minimalni omjer će odrediti vodeću liniju. Tabelu ponovo izračunavamo prema formulama, tj. idite na korak 3.
Grafička metoda je prilično jednostavna i jasna za rješavanje LP problema sa dvije varijable. Zasnovan je na geometrijski prikaz prihvatljivih rješenja i digitalni filter problema.
Svaka od nejednakosti LP problema definira se na koordinatnoj ravni (X 1 ,X 2 ) neke poluravni (slika 1), a sistem nejednačina kao celina je presek odgovarajućih ravni. Skup presječnih tačaka ovih poluravnina naziva se prihvatljivoodluke(ODR). ODR je uvijek konveksan figura, tj. koji ima sljedeće svojstvo: ako dvije tačke A i B pripadaju ovoj figuri, tada joj pripada cijeli segment AB. ODR se može grafički predstaviti konveksnim poligonom, neograničenom konveksnom poligonalnom površinom, segmentom, zrakom, jednom tačkom. U slučaju nekonzistentnosti sistema ograničenja problema, ODE je prazan skup.
Bilješka № 1. Sve navedeno važi i za slučaj kada sistem ograničenja (1.1) uključuje jednakosti, jer svaka jednakost
a il x 1 + a i 2 x 2 =b
može se predstaviti kao sistem od dvije nejednakosti (slika 1)
A i 2 x 2<Ь 1э +a i 2 x 2 >bj.
CF L(x)= s1h1 + s2h2 pri fiksnoj vrijednosti L(h)=L definira pravu liniju s1h1 na ravni + c2x2 = L. Promjenom vrijednosti L, dobijamo familiju paralelnih pravih, tzv. linije nivoa.
To je zbog činjenice da će promjena vrijednosti L samo promijeniti dužinu segmenta odsječenog linijom nivoa na osi x2 (početna ordinata), a nagib prave linije tga = -- će ostati konstanta (slika 1).
Stoga će za rješenje biti dovoljno konstruirati jednu od linija nivoa, proizvoljno birajući vrijednost L.
Vektor C = (c1;c2) sa koordinatama iz CF koeficijenata na x1 i x2 je okomit na svaku od linija nivoa (vidi sliku 1). Smjervektor C se poklapa sa smjerom povećanje CF, što je važna tačka za rešavanje problema. Smjer silazno CF suprotnosmjer vektora C.
Suština grafičke metode je sljedeća. U smjeru (protiv smjera) vektora C u ODS-u, potraga za optimalnom tačkom X = (x1; x2 ). Optimalna tačka je tačka kroz koju prolazi linija nivoa L max (L min), koja odgovara najvećoj (najmanjoj) vrednosti funkcije L (x). Optimalno rješenje se uvijek nalazi na ODT granici, na primjer, na posljednjem vrhu ODT poligona kroz koji prolazi ciljna linija, ili na cijeloj njegovoj strani.
Prilikom traženja optimalnog rješenja za probleme LP moguće su sljedeće situacije: postoji jedinstveno rješenje problema; postoji beskonačan broj rješenja (alternativni optium); CF nije ograničen; područje izvodljivih rješenja je jedna tačka; problem nema rješenje.
Dozvoljena površina - poluravan
Slika 1
1.2. Metodologija rješavanja LP zadataka grafičkom metodom
I. U okviru ograničenja problema, zamijenite znakove nejednakosti znakovima tačnih jednakosti i konstruirajte odgovarajuće prave.
II. Pronađite i zasjenčite poluravnine koje dozvoljava svaka od ograničenja nejednakosti problema. Da biste to učinili, zamijenite koordinate tačke [na primjer, (0; 0)] u određenu nejednakost i provjerite istinitost rezultirajuće nejednakosti.
Ako a prava nejednakost, onda potrebno je zasjeniti poluravninu koja sadrži datu tačku; inače (nejednakost je netačna) potrebno je zasjeniti poluravninu koja ne sadrži datu tačku.
Jer x1 i x2 moraju biti nenegativni, tada će njihove važeće vrijednosti uvijek biti iznad x1 ose i desno od ose x2, tj. u 1. kvadrantu.
Ograničenja jednakosti dozvoljavaju samo one tačke koje leže na odgovarajućoj liniji, pa odaberite takve linije na grafu.
Definirajte RDT kao dio ravni koji istovremeno pripada svim dozvoljenim područjima i odaberite ga. U nedostatku ODR-a, zadatak ne ima rješenja o čemu se izvlači odgovarajući zaključak.
Ako ODS nije prazan skup, konstruirajte ciljnu liniju, tj. bilo koja od linija nivoa sa 1 x 1 + sa 2 x 2 = L, gde je L proizvoljan broj, na primer, višekratnik od 1 i sa 2 , tj. pogodan za proračune. Metoda konstrukcije je slična konstrukciji direktnih ograničenja.
V. Konstruisati vektor C = (c 1 ,c 2) koji počinje u tački (0;0) i završava se u tački (c 1 ,c 2). Ako su ciljna linija i vektor C pravilno izgrađeni, onda će i biti su okomite.
VI. Kada tražite maksimalan CF, pomjerite ciljnu liniju u pravcu vektor C, kada se traži minimalni digitalni filter - protiv pravca vektor C. Last u smjeru kretanja, vrh ODR-a će biti točka max ili min digitalnog filtera. Ako ne postoji takva tačka(e), onda zaključi neograničenost digitalnog filtera uključena mnogo planova odozgo (kada se traži min) ili odozdo (kada se traži min).
Odredite koordinate tačke max (min) CF X = (x1 * ; x2 * ) i izračunajte vrijednost digitalnog filtera l(x *). Da biste izračunali koordinate optimalne tačke X *, rešite sistem jednačina pravih linija na čijem preseku se X * nalazi.
Zadatak 1
Nađimo optimalno rješenje problema čiji matematički model ima oblik
L(X) = 3x 1 + 2x 2 → max
x 1 + 2x 2< 6, (1)
2x 1 + x 2< 8, (2)
x 1 + x 2<1, (3)
x 2< 2, (4)
x 1 >0, x 2 >0.
Konstruirajmo direktna ograničenja, za koja izračunavamo koordinate tačaka preseka ovih pravih sa koordinatnim osama (slika 2).
x 1 + 2x 2 = 6,(1)
2x1+ x2=8,(2)
(1) x1=0, x1=6, x2=3, x2=0,
(2) x1=0, x1=4, x2=8, x2=0,
(3) x1=0, x1=-1, x2=1, x2=0,
Prava linija (4) prolazi kroz tačku x 2 = 2 paralelno sa osom L(X).
Rice. 2. Grafičko rješenje zadatka
Hajde da definišemo ODR. Na primjer, zamijenimo tačku (0;0) u originalno ograničenje (3), dobićemo 0< 1, что является истинным неравенством, поэтому стрелкой (или штрихованием) обозначим полуплоскость, koji sadrži tačka (0;0), tj. nalazi se desno i ispod prave linije (3). Slično, definiramo dopuštene poluravnine za preostala ograničenja i označavamo ih strelicama u blizini odgovarajućih direktnih ograničenja (slika 2). Ukupna površina dozvoljena svim ograničenjima, tj. ODR je poligon ABCDEF.
Ciljna linija se može konstruirati pomoću jednačine
Gradimo vektor C od tačke (0;0) do tačke (3;2). Tačka E je posljednji vrh poligona izvodljivih rješenja ABCDEF, kroz koji prolazi ciljna linija, krećući se prema vektor C. Dakle, E je maksimalna tačka digitalnog filtera. Odredimo koordinate tačke E iz sistema jednadžbi direktnih ograničenja (1) i (2)
X1 +2x 2 =6, (1) x1=10/3=3 1/3, x2=4/3=1 1/3
2 X1 + x 2 = 8, (2) E 3 1/3; 1 1/3
Maksimalna vrijednost digitalnog filtera je L(E) = 3*10/3+2*4/3 = 12 2 / 3
Razmotrimo prvo najjednostavniji slučaj, kada su u LLP uključene tačno dvije varijable:
Svaka od nejednačina (a)-(b) sistema ograničenja problema (3.8) geometrijski definiše poluravninu, respektivno, sa graničnim linijama , H 1 =0 i H 2 =0. Svaka od graničnih linija dijeli ravan x 1 x 2 na dvije poluravnine. Sva rješenja izvorne nejednakosti leže u jednoj od formiranih poluravnina (sve točke poluravnine) i, stoga, kada se koordinate bilo koje njene točke zamijene u odgovarajuću nejednačinu, ona je pretvara u pravi identitet . Imajući to na umu, određuje se poluravnina u kojoj leže rješenja nejednakosti, tj. odabirom bilo koje tačke iz bilo koje poluravnine i zamjenom njenih koordinata u odgovarajuću nejednačinu. Ako nejednakost vrijedi za datu tačku, onda vrijedi i za bilo koju drugu tačku iz iste poluravni. Inače, rješenja nejednačine leže u drugoj poluravni.
U slučaju da je sistem nejednačina (a)-(b) konzistentan, tada je domen njegovih rješenja skup tačaka koje pripadaju svim naznačenim poluravnama. Budući da je skup presječnih točaka ovih poluravnina konveksan, domena izvodljivih rješenja problema (3.8) je konveksan skup, koji se naziva poligon rješenja (ranije uveden izraz „poliedar rješenja“ obično se koristi ako je n 3 ). Stranice ovog poligona leže na pravim linijama čije se jednačine dobijaju iz originalnog sistema ograničenja zamjenom znakova nejednakosti znakovima tačnih jednakosti.
Dakle, originalni LLP se sastoji u pronalaženju takve tačke poligona odluke u kojoj ciljna funkcija F zauzima maksimalnu (minimalnu) vrijednost.
Ova tačka postoji kada poligon rješenja nije prazan i ciljna funkcija na njemu je ograničena odozgo. Pod ovim uslovima, na jednom od vrhova poligona odluke, funkcija cilja zauzima maksimalnu vrednost. Da bi se odredio ovaj vrh, gradi se linija nivoa L: c 1 x 1 + c 2 x 2 = h (gdje je h neka konstanta), okomita na vektor gradijenta i prolazi kroz poligon rješenja, te ga pomiče paralelno duž vektor gradijenta sve dok ne prođe svoju posljednju zajedničku tačku presjeka sa poligonom rješenja (prilikom konstruiranja vektora gradijenta, tačka (c 1; c 2) se odloži u ravnini x 1 Ox 2 i nacrta se usmjereni segment na to od porijekla). Koordinate navedene tačke određuju optimalni plan za ovaj zadatak.
Sumirajući sve navedeno, predstavljamo algoritam za grafičku metodu rješavanja LLP.
Algoritam grafičke metode za rješavanje LLP
1. Konstruirajte poligon odluke zadan sistemom ograničenja originalnog LLP.
2. Ako je konstruirani poligon rješenja prazan skup, onda originalni LLP nema rješenja. U suprotnom, konstruisati gradijent vektor i nacrtati proizvoljnu liniju nivoa L, pomerajući se koja, pri rešavanju problema do maksimuma u pravcu vektora (ili u suprotnom smeru za zadatak do minimuma), određuje ekstremnu tačku poligon rješenja, gdje se postiže maksimum (minimum) ciljne funkcije problema.
3. Izračunati koordinate pronađene optimalne tačke rješavanjem sistema jednačina dvije granične linije koje se u njoj seku.
4. Zamjenom pronađenog optimalnog rješenja u ciljnu funkciju problema izračunati njegovu optimalnu vrijednost, tj.: .
Prilikom grafičkog konstruisanja skupa izvodljivih rješenja LLP-a (poligon rješenja) moguće su sljedeće situacije.
Matematičko modeliranje u operativnim istraživanjima je, s jedne strane, veoma važan i složen proces, as druge strane, praktično nije podložan naučnoj formalizaciji. Treba napomenuti da su ponovljeni pokušaji da se identifikuju opšti principi za kreiranje matematičkih modela doveli ili do deklarisanja preporuka najopštije prirode, koje je teško primeniti na rešavanje specifičnih problema, ili, obrnuto, do pojave recepata koji su zapravo primjenjive samo na uski raspon problema. Stoga je korisnije upoznati se s tehnikom matematičkog modeliranja na konkretnim primjerima.
Problemi linearnog programiranja mogu se riješiti sljedećim metodama:
Floydov algoritam;
Dijkstrin algoritam na grafovima;
grafička metoda;
metoda simpleks tabele itd.
Algoritam za rješavanje problema linearnog programiranja Dijkstrinom metodom na grafovima.
U najjednostavnijoj implementaciji, niz brojeva se može koristiti za pohranjivanje brojeva d[i], a niz Booleovih varijabli može se koristiti za pohranjivanje članstva elementa u skupu U.
Na početku algoritma se pretpostavlja da je udaljenost za početni vrh nula, a sve ostale udaljenosti su ispunjene velikim pozitivnim brojem (većim od maksimalno mogućeg puta u grafu). Niz zastavice je ispunjen nulama. Tada počinje glavna petlja.
Na svakom koraku petlje potrebno je pronaći vrh U sa minimalnom udaljenosti i zastavicom jednakom nuli. Zatim trebate postaviti zastavicu u njoj na 1 i provjeriti sve vrhove U koji su susjedni uz njega. Ako je udaljenost veća od zbira udaljenosti do trenutnog vrha i dužine ivice, onda je trebate smanjiti. Petlja se završava kada zastavice svih vrhova postanu jednake 1, ili kada svi vrhovi imaju zastavicu 0. Potonji slučaj je moguć ako i samo ako graf G nije povezan.
Način rješavanja problema linearnog programiranja grafičkom metodom.
Grafička metoda za rješavanje problema linearnog programiranja zasniva se na geometrijskoj interpretaciji problema linearnog programiranja i uglavnom se koristi za rješavanje problema u dvodimenzionalnom prostoru i samo nekih problema u trodimenzionalnom prostoru, jer je prilično teško konstruirati poliedar rješenja koji nastaje kao rezultat presjeka poluprostora. Zadatak prostora dimenzija većih od tri uopće se ne može grafički prikazati.
Neka je problem linearnog programiranja zadan u dvodimenzionalnom prostoru, tj. ograničenja sadrže dvije varijable.
Minimalna vrijednost funkcije određena je formulom (1).
(1)
Ograničenja su predstavljena formulama (2) i (3).
(2)
(3)
Neka je sistem (2) pod uslovom (3) konzistentan. Svaka od nejednačina iz sistema (2) i (3) definira poluravninu sa graničnim linijama predstavljena je formulom (4):
Linearna funkcija (1) pri fiksnim vrijednostima Z je jednačina prave linije: 
Potrebno je konstruisati poligon rješenja sistema ograničenja (2) i graf linearne funkcije (1) na Z=0. Tada se postavljenom problemu linearnog programiranja može dati sljedeća interpretacija:
Pronađite tačku poligona rješenja u kojoj je linija 
a funkcija Z u ovom slučaju dostiže minimum.
Vrijednosti 
smanjenje u smjeru vektora 
, pa se prava Z=0 mora pomjeriti paralelno sa sobom u smjeru vektora N.
Ako je poligon odluke omeđen, tada linija dvaput postaje linija oslonca u odnosu na poligon odluke (u tačkama B i E), a minimalna vrijednost se uzima u tački E. Koordinate tačke 
mora se naći rješavanjem sistema jednačina pravih DE i EF.
Ako je poligon rješenja neograničeno poligonalno područje, tada su moguća dva slučaja.
Slučaj 1. Direktno 
, krećući se u smjeru vektora N ili suprotno od njega, stalno siječe poligon rješenja i ni u jednoj tački nije referenca na njega. U ovom slučaju, linearna funkcija je neograničena na poligonu rješenja i iznad i ispod.
Slučaj 2. Prava linija, krećući se, ipak postaje oslonac u odnosu na poligon rješenja. Zatim, ovisno o vrsti domene, linearna funkcija može biti ograničena odozgo i neograničena odozdo, ograničena odozdo i neograničena odozgo, ili ograničena i odozdo i odozgo.
Za rješavanje ovog problema najpoznatija i najšire korištena u praksi za rješavanje problema linearnog programiranja je simpleks metoda. Uprkos činjenici da je simpleks metoda prilično efikasan algoritam koji je pokazao dobre rezultate u rješavanju problema primijenjenog linearnog programiranja, riječ je o algoritmu eksponencijalne složenosti.
Simpleks metoda problema linearnog programiranja zasniva se na prijelazu s jednog plana podrške na drugi, u kojem se vrijednost ciljne funkcije povećava ili smanjuje.
Prije sastavljanja simpleks tablice, problem se mora transformirati, sistem ograničenja svesti na prihvatljivu osnovnu formu, uz pomoć koje se osnovne varijable moraju isključiti iz funkcije cilja, kao što je prikazano na slici 1.
Slika 1 - Početna transformacija sistema ograničenja
Ovdje se, radi određenosti notacije, pretpostavlja da se varijable X1, X2, ..., Xr mogu uzeti kao osnovne varijable i da su u ovom slučaju b1, b2, ..., br ≥ 0 (odgovarajuća osnovna rješenje je referentno).
Za sastavljanje simpleks tabele, u svim jednakostima u uslovu zadatka, članovi koji sadrže varijable se prenose na lijevu stranu, slobodni se ostavljaju na desnu, tj. Problem je napisan kao sistem jednačina kao što je prikazano na slici 2.
Slika 2 - Transformacija sistema nejednakosti
Algoritam za prelazak na sljedeću tabelu je sljedeći:
pregleda se zadnji red (indeks) tabele i među koeficijentima ovog reda (isključujući kolonu slobodnih članova) bira se najmanji negativan broj pri pronalaženju max, odnosno najveći pozitivan broj kada se zadaju za min. Ako ga nema, onda je originalno osnovno rješenje optimalno i ova tabela je posljednja;
gleda se kolona tabele koja odgovara izabranom negativnom (pozitivnom) koeficijentu u poslednjem redu - ključna kolona, au ovoj koloni se biraju pozitivni koeficijenti. Ako ih nema, onda je ciljna funkcija neograničena na raspon dozvoljenih vrijednosti varijabli i problem nema rješenja;
među izabranim koeficijentima stupaca se bira onaj za koji je minimalna apsolutna vrijednost odnosa odgovarajućeg slobodnog termina (koja se nalazi u koloni slobodnih termina) prema ovom elementu. Ovaj koeficijent se zove rješavanje, a linija u kojoj se nalazi je ključna;
ubuduće, osnovna varijabla koja odgovara redu elementa omogućavanja mora biti prebačena u kategoriju slobodnih, a slobodna varijabla koja odgovara stupcu elementa omogućavanja mora biti uključena u broj osnovnih. Izgrađena je nova tabela koja sadrži nova imena osnovnih varijabli:
dijelimo svaki element ključnog reda (isključujući kolonu slobodnih članova) na razrješavajući element i rezultujuće vrijednosti upisujemo u red s promijenjenom osnovnom varijablom nove simpleks tablice.
niz elementa koji dozvoljava je podijeljen ovim elementom i rezultirajući niz se upisuje u novu tablicu na istom mjestu.
u novoj tabeli svi elementi ključnog stupca = 0, osim reznog, uvijek je jednak 1.
kolona koja ima 0 u ključnom redu bit će ista u novoj tabeli.
red koji ima 0 u ključnoj koloni će biti isti u novoj tabeli.
rezultat transformacije elemenata stare tabele se beleži u preostale ćelije nove tabele, kao što je prikazano na slici 3.
Slika 3 - Kompilacija novog elementa u simpleks tabeli
Kao rezultat, dobija se nova simpleks tabela koja odgovara novom osnovnom rješenju.
Sada biste trebali pogledati liniju ciljne funkcije (indeks), ako ne sadrži negativne vrijednosti (u problemu pronalaženja maksimalne vrijednosti), ili pozitivne vrijednosti (u problemu pronalaženja minimalne vrijednosti) osim mirovanja (slobodna kolona), onda to znači da je dobijeno optimalno rješenje. U suprotnom, prelazimo na novu simpleks tablicu prema gore opisanom algoritmu.
Za rješavanje problema ovog kursnog rada odabran je pravac problema optimalne raspodjele sredstava u preduzeću. Optimalni plan ili optimalno rješenje problema linearnog programiranja je plan u kojem će se vrijednost cilja povećati (smanjiti).
Nakon analize prikupljenih informacija, sastavljen je problem linearnog programiranja za radnju broj 8 pri NefAZ OJSC.Na lakirskoj traci na kojoj se farbaju dijelovi. Potrebno je farbati optimalan broj dijelova u jednoj radnoj smjeni kako bi se maksimizirao profit.
Za dalje rješavanje problema potrebno je formulirati iskaz problema i matematički model problema.
U linearnom programiranju, grafička metoda se koristi za određivanje konveksnih skupova (poliedar rješenja). Ako glavni problem linearnog programiranja ima optimalan plan, tada funkcija cilja uzima vrijednost na jednom od vrhova poliedra odluke (vidi sliku).
Servisni zadatak. Koristeći ovu uslugu, možete riješiti problem linearnog programiranja geometrijskom metodom na mreži, kao i dobiti rješenje dualnog problema (procijeniti optimalno korištenje resursa). Osim toga, u Excelu se kreira predložak rješenja.
Uputstvo. Odaberite broj redova (broj ograničenja). Ako je broj varijabli veći od dvije, potrebno je dovesti sistem u SZLP (vidi i primjer br. 2). Ako je ograničenje dvostruko, na primjer, 1 ≤ x 1 ≤ 4, tada se dijeli na dva: x 1 ≥ 1, x 1 ≤ 4 (to jest, broj redova se povećava za 1).
Također možete izgraditi područje izvodljivog rješenja (DDR) koristeći ovu uslugu.
Sa ovim kalkulatorom se također koriste sljedeće:
Simpleksna metoda za rješavanje LLP
Rješenje transportnog problema
Rešenje matrične igre
Koristeći online uslugu, možete odrediti cijenu matrične igre (donje i gornje granice), provjeriti sedlo, pronaći rješenje za mješovitu strategiju koristeći sljedeće metode: minimaks, simpleks metoda, grafička (geometrijska) metoda, Brownova metoda.
Ekstremum funkcije dvije varijable
Limit Calculation
Rješavanje problema linearnog programiranja grafičkom metodom uključuje sljedeće korake:
- Linije se grade na ravni X 1 0X 2.
- Definisane su poluravnine.
- Definirajte poligon odluke;
- Izgraditi vektor N(c 1 ,c 2), koji ukazuje na smjer ciljne funkcije;
- Pomjerite direktnu ciljnu funkciju c 1 x 2 + c 2 x 2= 0 u pravcu vektora N do krajnje tačke poligona rješenja.
- Izračunajte koordinate tačke i vrijednost funkcije cilja u ovoj tački.
Primjer. Kompanija proizvodi dvije vrste proizvoda - P1 i P2. Za proizvodnju proizvoda koriste se dvije vrste sirovina - C1 i C2. Veleprodajna cijena jedinice proizvodnje jednaka je: 5 CU za P1 i 4 k.u. za P2. Potrošnja sirovina po jedinici proizvodnje tipa P1 i tipa P2 data je u tabeli.
Tabela - Potrošnja sirovina za proizvodnju
Potrebno je utvrditi:
Koliko proizvoda svake vrste kompanija treba da proizvede da bi maksimizirala prihod od prodaje proizvoda?
- Formulirati matematički model problema linearnog programiranja.
- Riješite problem linearnog programiranja grafički (za dvije varijable).
Hajde da formulišemo matematički model problema linearnog programiranja.
x 1 - proizvodnja P1, jed.
x 2 - proizvodnja P2 proizvoda, jedinica.
x 1 , x 2 ≥ 0
Ograničenja resursa
6x1 + 4x2 ≤ 24
x1 + 2x2 ≤ 6
Ograničenja potražnje
x 1 +1 ≥ x 2
x2 ≤ 2
ciljna funkcija
5x1 + 4x2 → max
Tada dobijamo sljedeće LLP:
6x1 + 4x2 ≤ 24
x1 + 2x2 ≤ 6
x 2 - x 1 ≤ 1
x2 ≤ 2
x 1 , x 2 ≥ 0
5x1 + 4x2 → max
Ako je broj varijabli u problemu linearnog programiranja veći od dvije, tada se problem prvo svodi na standardni LLP.
→ max uz ograničenja:
x1 + x2 + x3 =12
2x 1 - x 2 + x 4 = 8
- 2x 1 + 2x 2 + x 5 =10
F(X) = 3x 1 - 2x 2 + 5x 3 - 4x 5
Prelazak na SZLP.
| 1 | 1 | 1 | 0 | 0 | 12 |
| 2 | -1 | 0 | 1 | 0 | 8 |
| -2 | 2 | 0 | 0 | 1 | 10 |
Svedujmo sistem na matricu identiteta metodom jordanskih transformacija.
x1 + x2 + x3 = 12
2x1 - x2 + x4 = 8
- 2x 1 + 2x 2 + x 5 = 10
x 3 \u003d - x 1 - x 2 +12
x 4 = - 2x 1 + x 2 +8
x 5 = 2x 1 - 2x 2 +10
ili
Sistem nejednakosti:
- x 1 - x 2 +12 ≥ 0
- 2x 1 + x 2 +8 ≥ 0
2x 1 - 2x 2 +10 ≥ 0
x1 + x2 ≤ 12
2x1 - x2 ≤ 8
- 2x1 + 2x2 ≤ 10
Osobine rješavanja zadataka linearnog programiranja grafičkom metodom
Primjer #1. Napišite problem u standardnom obliku i riješite ga grafički.f=x 1 +13x 2 -x 3 +2x 4 +3x 5
-x 2 +x 3 -x 5 =-3
x 1 -4x 2 +3x 3 -x 4 +2x 5 =3
4x 2 -x 3 +x 4 -x 5 =6
Iz prve jednačine izražavamo x 5:
x5 = -x2 +x3 +3
f=x 1 +13x 2 -x 3 +2x 4 +3(-x 2 +x 3 +3)
x 1 -4x 2 +3x 3 -x 4 +2(-x 2 +x 3 +3)=3
4x 2 -x 3 +x 4 -(-x 2 +x 3 +3)=6
ili
f=x 1 +10x 2 +2x 3 +2x 4 +9
x 1 -6x 2 +5x 3 -x 4 =-3
5x2 -2x3 +x4 =9
Iz druge jednačine izražavamo x 4:
x 4 \u003d 9-5x 2 + 2x 3
i zamijeni u svim izrazima:
f=x 1 +6x 3 +27
x 1 -x 2 +3x 3 =6
Prihvatamo varijablu x 2 kao dodatnu varijablu i pravimo zamjenu za znak “≥”:
f=x 1 + 6x 3 + 27
x 1 + 3x 3 ≥6
Primjer #2
x1 + x2 + x3 =12
2x 1 - x 2 + x 4 = 8
- 2x 1 + 2x 2 + x 5 =10
F(X) = 3x 1 - 2x 2 + 5x 3 - 4x 5
Prelazak na SZLP.
Proširena matrica sistema ograničenja-jednakosti ovog problema:
| 1 | 1 | 1 | 0 | 0 | 12 |
| 2 | -1 | 0 | 1 | 0 | 8 |
| -2 | 2 | 0 | 0 | 1 | 10 |
1. Možete odabrati x 3 kao osnovnu varijablu.
2. Možete odabrati x 4 kao osnovnu varijablu.
3. Možete odabrati x 5 kao osnovnu varijablu.
Pošto sistem ima matricu identiteta, uzimamo X = (3,4,5) kao osnovne varijable.
Odgovarajuće jednačine su:
x1 + x2 + x3 = 12
2x1 - x2 + x4 = 8
- 2x 1 + 2x 2 + x 5 = 10
Osnovne varijable izražavamo u terminima ostatka:
x 3 \u003d - x 1 - x 2 +12
x 4 = - 2x 1 + x 2 +8
x 5 = 2x 1 - 2x 2 +10
Zamijenite ih u funkciju cilja:
F(X) = 3x 1 - 2x 2 + 5(- x 1 - x 2 +12) - 4(2x 1 - 2x 2 +10)
ili
F(X) = - 10x 1 + x 2 +20 → max
Sistem nejednakosti:
- x 1 - x 2 +12 ≥ 0
- 2x 1 + x 2 +8 ≥ 0
2x 1 - 2x 2 +10 ≥ 0
Sistem nejednačina dovodimo u sljedeći oblik:
x1 + x2 ≤ 12
2x1 - x2 ≤ 8
- 2x1 + 2x2 ≤ 10
F(X) = - 10x 1 + x 2 +20 → max
Primjer #3. Sastaviti matematički model problema linearnog programiranja i pronaći rješenje na geometrijski način.
- Sastaviti sistem matematičkih zavisnosti (nejednakosti) i ciljnu funkciju.
- Predstavite geometrijsku interpretaciju problema.
- Pronađite optimalno rješenje.
- Izvršite analitičku provjeru.
- Identifikujte bitne i nebitne resurse i njihove viškove.
- Odrediti vrijednost ciljne funkcije.
- Izračunajte objektivno određene procjene.
- Sastavite omjer stabilnosti.
