Sviđa mi se? Dodaj u oznake

Rješavanje zadataka simpleks metodom: online primjeri

Zadatak 1. Tvrtka proizvodi kupaonske police u dvije veličine - A i B. Prodajni agenti procjenjuju da se tjedno na tržištu može prodati do 550 polica. Za svaku policu tipa A potrebno je 2 m2 materijala, a za svaku policu tipa B potrebno je 3 m2 materijala. Tvrtka može primiti do 1200 m2 materijala tjedno. Za izradu jedne police tipa A potrebno je 12 minuta strojnog vremena, a za izradu jedne police tipa B 30 minuta; Stroj se može koristiti 160 sati tjedno. Ako je dobit od prodaje polica tipa A 3 novčane jedinice, a od polica tipa B - 4 novčane jedinice. jedinica, onda koliko bi polica svake vrste trebalo biti proizvedeno tjedno?

Zadatak 2. Rješavanje problema linearnog programiranja koristeći simpleks metodu.

Zadatak 3. Tvrtka proizvodi 3 vrste proizvoda: A1, A2, A3, koristeći dvije vrste sirovina. Poznati su troškovi svake vrste sirovina po jedinici proizvodnje, zalihe sirovina za plansko razdoblje, kao i dobit od jedinice proizvodnje svake vrste.

1. Koliko predmeta svake vrste mora biti proizvedeno da bi se maksimizirao profit?
2. Odrediti status svake vrste sirovine i njezinu specifičnu vrijednost.
3. Odrediti maksimalni interval promjena zaliha svake vrste sirovina unutar kojeg je struktura optimalnog plana, tj. Proizvodna nomenklatura se neće mijenjati.
4. Odredite količinu proizvedenih proizvoda i dobit od proizvodnje pri povećanju zaliha jedne od deficitarnih vrsta sirovina na najveću moguću (unutar zadanog opsega proizvodnje) vrijednost.
5. Odredite intervale promjene dobiti od jedinice proizvodnje svake vrste u kojima se rezultirajući optimalni plan neće mijenjati.

Zadatak 4. Riješite problem linearnog programiranja koristeći simpleks metodu:

Zadatak 5. Riješite problem linearnog programiranja koristeći simpleks metodu:

Zadatak 6. Riješite zadatak koristeći simpleks metodu, uzimajući kao početni referentni plan plan zadan u uvjetu:

Zadatak 7. Riješite zadatak modificiranom simpleks metodom.
Za proizvodnju dvije vrste proizvoda A i B koriste se tri vrste tehnološke opreme. Za proizvodnju jedinice proizvoda A oprema prve vrste troši a1=4 sata, oprema druge vrste a2=8 sati, a oprema treće vrste a3=9 sati. Za proizvodnju jedinice proizvoda B oprema prve vrste troši b1=7 sati, oprema druge vrste b2=3 sata, a oprema treće vrste b3=5 sati.
Oprema prve vrste može raditi za proizvodnju ovih proizvoda najviše t1=49 sati, oprema druge vrste ne više od t2=51 sat, oprema treće vrste ne više od t3=45 sati.
Dobit od prodaje jedinice gotovog proizvoda A je ALPHA = 6 rubalja, a proizvod B je BETTA = 5 rubalja.
Napravite plan proizvodnje proizvoda A i B, osiguravajući maksimalnu dobit od njihove prodaje.

Zadatak 8. Pronađite optimalno rješenje pomoću dualne simpleks metode

Problemi linearnog programiranja. To je u sekvencijalnoj konstrukciji koja karakterizira proces koji se razmatra. Rješenje je podijeljeno u tri glavne faze: izbor varijabli, konstrukcija sustava ograničenja i traženje funkcije cilja.

Na temelju ove podjele, uvjet problema može se preformulirati na sljedeći način: ekstrem funkcije cilja Z(X) = f(x1, x2, … ,xn) → max (min) i odgovarajuće varijable, ako je poznato da one zadovoljavaju sustav ograničenja: Φ_i ( x1, x2, … ,xn) = 0 za i = 1, 2, …, k; Φ_i (x1, x2, … ,xn)) 0 za i = k+1, k+ 2, …, m.

Sustav ograničenja mora se dovesti u kanonski oblik, tj. sustavu linearnih jednadžbi, gdje je broj varijabli veći od broja jednadžbi (m > k). U ovom sustavu sigurno će postojati varijable koje se mogu izraziti kroz druge varijable, a ako to nije slučaj, onda se one mogu unijeti umjetno. U tom se slučaju prvi nazivaju osnova ili umjetna osnova, a drugi se nazivaju slobodni.

Pogodnije je razmotriti simpleks metodu koristeći određeni primjer. Neka je zadana linearna funkcija f(x) = 6x1 + 5x2 + 9x3 i sustav ograničenja: 5x1 + 2x2 + 3x3 ≤ 25; x1 + 6x2 + 2x3 ≤ 20; 4x1 + 3x3 ≤ 18. Trebamo pronaći maksimum vrijednost funkcije f(x).

Rješenje U prvoj fazi zadajte početno (referentno) rješenje sustava jednadžbi na apsolutno proizvoljan način, koje mora zadovoljiti zadani sustav ograničenja. U ovom slučaju potrebno je uvođenje umjetnog, tj. osnovne varijable x4, x5 i x6 na sljedeći način: 5x1 + 2x2 + 3x3 + x4 = 25; x1 + 6x2 + 2x3 + x5 = 20; 4x1 + 3x3 + x6 = 18.

Kao što vidite, nejednadžbe su pretvorene u jednakosti zahvaljujući dodanim varijablama x4, x5, x6, koje su nenegativne veličine. Time ste doveli sustav u njegovu kanonsku formu. Varijabla x4 je uključena u prvu jednadžbu s koeficijentom 1, au drugu jednadžbu s koeficijentom 0, isto vrijedi i za varijable x5, x6 i pripadajuće jednadžbe, što odgovara definiciji baze.

Pripremili ste sustav i pronašli početno referentno rješenje – X0 = (0, 0, 0, 25, 20, 18). Sada predstavite koeficijente varijabli i slobodne članove jednadžbi (brojeve desno od znaka “=”) u obliku tablice kako biste optimizirali daljnje izračune (vidi sliku).

Bit simpleks metode je dovesti ovu tablicu u oblik u kojem će svi brojevi u retku L biti nenegativne vrijednosti. Ako se pokaže da je to nemoguće, onda sustav uopće nema optimalno rješenje. Prvo odaberite najmanji element ove linije, a to je -9. Broj je u trećem stupcu. Pretvorite odgovarajuću x3 varijablu u baznu varijablu. Da biste to učinili, liniju podijelite s 3 tako da ćelija završi s 1.

Sada trebate ćelije i okrenuti se na 0. Da biste to učinili, oduzmite od odgovarajućih brojeva trećeg retka za 3. Od elemenata drugog retka - elemente trećeg, pomnoženo s 2. I, konačno, od elementi reda L - pomnoženi s (-9). Dobili ste drugo referentno rješenje: f(x) = L = 54 s x1 = (0, 0, 6, 7, 8, 0).

Razmotrimo simpleks metoda za rješavanje problema linearnog programiranja (LP). Temelji se na prijelazu s jednog referentnog plana na drugi, pri čemu vrijednost funkcije cilja raste.

Algoritam simpleks metode je sljedeći:

1. Izvorni problem pretvaramo u kanonski oblik uvođenjem dodatnih varijabli. Za nejednadžbe oblika ≤ uvode se dodatne varijable sa predznakom (+), ali ako su oblika ≥ onda sa predznakom (-). Dodatne varijable uvode se u funkciju cilja s odgovarajućim predznacima s koeficijentom jednakim 0 , jer ciljna funkcija ne bi trebala mijenjati svoje ekonomsko značenje.
2. Vektori su ispisani P i iz koeficijenata varijabli i stupca slobodnih članova. Ova akcija određuje broj jediničnih vektora. Pravilo je da treba biti onoliko jediničnih vektora koliko ima nejednakosti u sustavu ograničenja.
3. Nakon toga se izvorni podaci unose u simpleks tablicu. U bazu se uvode jedinični vektori, a njihovim isključivanjem iz baze nalazi se optimalno rješenje. Koeficijenti funkcije cilja zapisani su sa suprotnim predznakom.
4. Znak optimalnosti za LP problem je da je rješenje optimalno ako je u f– u nizu su svi koeficijenti pozitivni. Pravilo za pronalaženje stupca za omogućavanje - pregledano f– niz i među njegovim negativnim elementima odabire se najmanji. Vektor P i njegovo sadržavanje postaje dopušteno. Pravilo za izbor rezolirajućeg elementa - sastavljaju se omjeri pozitivnih elemenata rezolirajućeg stupca prema elementima vektora. P 0 a broj koji daje najmanji omjer postaje razlučujući element s obzirom na koji će se ponovno izračunati simpleksna tablica. Linija koja sadrži ovaj element naziva se linija za uključivanje. Ako nema pozitivnih elemenata u stupcu rješenja, onda problem nema rješenja. Nakon određivanja razrješujućeg elementa, prelazi se na ponovno izračunavanje nove simpleks tablice.
5. Pravila za popunjavanje nove simplex tablice. Jedinica se stavlja umjesto razrješujućeg elementa, a ostali elementi se smatraju jednakima 0 . Bazici se dodaje razlučujući vektor iz kojeg se isključuje odgovarajući nulti vektor, a preostali bazni vektori zapisuju se bez promjena. Elementi linije rezolucije dijele se elementom rezolucije, a preostali elementi se preračunavaju prema pravilu pravokutnika.
6. Ovo se radi do f– svi elementi niza neće postati pozitivni.

Razmotrimo rješavanje problema korištenjem algoritma koji je gore opisan.
dano:

Dovodimo problem u kanonski oblik:

Sastavljamo vektore:

Ispunite simpleks tablicu:

:
Preračunajmo prvi element vektora P 0, za koji napravimo pravokutnik od brojeva: i dobijemo: .

Izvodimo slične izračune za sve ostale elemente simpleks tablice:

U primljenom planu f– linija sadrži jedan negativan element – ​​​​(-5/3), vektor P 1. U svom stupcu sadrži jedan pozitivan element, koji će biti pokretački element. Preračunajmo tablicu u vezi s ovim elementom:

Nema negativnih elemenata f– crta znači pronađeno optimalan plan:
F* = 36/5, X = (12/5, 14/5, 8, 0, 0).

• Ashmanov S. A. Linearno programiranje, M: Nauka, 1998,
• Ventzel E.S. Operacijska istraživanja, M: Sovjetski radio, 2001.,
• Kuznetsov Yu.N., Kuzubov V.I., Voloshenko A.B. Matematičko programiranje, M: Viša škola, 1986.

Prilagođeno rješenje za linearno programiranje

Sve zadatke iz ove discipline možete naručiti na našoj web stranici. Možete priložiti datoteke i odrediti rokove na

Ovdje je ručno (ne applet) rješenje dvaju problema korištenjem simplex metode (slično rješenju appleta) s detaljnim objašnjenjima kako bi se razumio algoritam za rješavanje problema korištenjem simplex metode. Prvi zadatak sadrži znakove nejednakosti samo “≤” (problem s početnom bazom), drugi može sadržavati znakove “≥”, “≤” ili “=” (problem s umjetnom bazom), različito se rješavaju.

Simpleksna metoda, rješavanje problema s početnom bazom

1)Simpleks metoda za problem s početnom bazom (svi znakovi nejednakosti ograničenja " ≤ ").

Upišimo problem kanonski obliku, tj. prepisujemo ograničenja nejednakosti u obliku jednakosti, dodajući bilanca stanja varijable:

Ovaj sustav je sustav s bazom (baze s 1, s 2, s 3, svaka od njih je uključena u samo jednu jednadžbu sustava s koeficijentom 1), x 1 i x 2 su slobodne varijable. Problemi koji se rješavaju simpleks metodom moraju imati sljedeća dva svojstva: - sustav ograničenja mora biti sustav jednadžbi s bazom; -slobodni članovi svih jednadžbi u sustavu moraju biti nenegativni.

Rezultirajući sustav je sustav s bazom i njegovi slobodni članovi su nenegativni, tako da se možemo primijeniti simpleks metoda. Kreirajmo prvu simpleks tablicu (Iteracija 0) za rješavanje problema simpleks metoda, tj. tablicu koeficijenata funkcije cilja i sustav jednadžbi za pripadajuće varijable. Ovdje "BP" znači stupac osnovnih varijabli, "Rješenje" znači stupac desnih strana jednadžbi sustava. Rješenje nije optimalno, jer postoje negativni koeficijenti u z-retku.

iteracija simpleks metode 0

							Stav

Kako bismo poboljšali rješenje, prijeđimo na sljedeću iteraciju simpleks metoda, dobivamo sljedeću simpleks tablicu. Da biste to učinili, morate odabrati omogućiti stupac, tj. varijabla koja će biti uključena u bazu pri sljedećoj iteraciji simpleks metode. Odabire se prema najvećem apsolutnom negativnom koeficijentu u z-retku (u maksimalnom problemu) - u početnoj iteraciji simpleks metode to je stupac x 2 (koeficijent -6).

Zatim odaberite omogućiti niz, tj. varijablu koja će napustiti bazu pri sljedećoj iteraciji simpleks metode. Odabire se prema najmanjem omjeru stupca “Odluka” prema odgovarajućim pozitivnim elementima stupca rezolucije (stupac “Omjer”) - u početnoj iteraciji to je red s 3 (koeficijent 20).

Permisivni element nalazi se na sjecištu razlučujućeg stupca i razlučujućeg retka, njegova ćelija je označena bojom, jednaka je 1. Stoga će pri sljedećoj iteraciji simpleks metode varijabla x 2 zamijeniti s 1 u bazi. Imajte na umu da se odnos ne traži u z-stringu; ondje se stavlja crtica "-". Ako postoje identični minimalni odnosi, odabire se bilo koji od njih. Ako su svi koeficijenti u stupcu rezolucije manji ili jednaki 0, tada je rješenje problema beskonačno.

Ispunimo sljedeću tablicu “Iteracija 1”. Dobit ćemo ga iz tablice “Iteration 0”. Cilj daljnjih transformacija je pretvoriti stupac rezolucije x2 u stupac jedinice (s jedinicom umjesto elementa rezolucije i nulama umjesto preostalih elemenata).

1) Izračunajte redak x 2 tablice "Iteracija 1". Prvo, podijelimo sve članove razrješavajućeg retka s 3 tablice "Iteracija 0" s razlučujućim elementom (on je u ovom slučaju jednak 1) ove tablice, dobivamo redak x 2 u tablici "Iteracija 1" . Jer razlučujući element u ovom slučaju jednak je 1, tada će se red s 3 tablice "Iteracija 0" podudarati s retkom x 2 tablice "Iteracija 1". Red x 2 tablice Iteracije 1 dobili smo 0 1 0 0 1 20, preostali redovi tablice Iteracije 1 bit će dobiveni iz ovog retka i redaka tablice Iteracije 0 kako slijedi:

2) Izračun z-retka tablice "Iteracija 1". Umjesto -6 u prvom retku (z-redak) u stupcu x2 tablice Iteracije 0, treba postojati 0 u prvom retku tablice Iteracije 1. Da biste to učinili, pomnožite sve elemente retka x 2 tablice "Iteracija 1" 0 1 0 0 1 20 sa 6, dobit ćemo 0 6 0 0 6 120 i zbrojite ovaj red s prvim redom (z - red) tablice "Iteracija 0" -4 -6 0 0 0 0, dobivamo -4 0 0 0 6 120. U stupcu x 2 pojavljuje se nula 0, cilj je postignut. Elementi stupca rezolucije x 2 označeni su crvenom bojom.

3) Izračun retka s 1 tablice "Iteracija 1". Umjesto 1 u prvom retku tablice "Iteracija 0" trebala bi stajati 0 u tablici "Iteracija 1". Da biste to učinili, pomnožite sve elemente retka x 2 tablice "Iteracija 1" 0 1 0 0 1 20 s -1, dobijete 0 -1 0 0 -1 -20 i dodajte ovaj red sa s 1 - redom tablici "Iteration 0" 2 1 1 0 0 64, dobivamo redak 2 0 1 0 -1 44. U stupcu x 2 dobivamo traženu 0.

4) Izračunajte red s 2 u tablici "Iteracija 1". Na mjestu 3 u s 2 retku tablice "Iteracija 0" treba biti 0 u tablici "Iteracija 1". Da biste to učinili, pomnožite sve elemente retka x 2 tablice "Iteracija 1" 0 1 0 0 1 20 s -3, dobit ćemo 0 -3 0 0 -3 -60 i dodajte ovaj red sa s 1 - retkom od tablici "Iteracija 0" 1 3 0 1 0 72, dobivamo redak 1 0 0 1 -3 12. U stupcu x 2 dobiven je traženi stupac 0 u tablici “Iteracija 1”. jedinica, sadrži jednu 1, a ostatak 0.

Redovi tablice "Iteracija 1" dobivaju se prema sljedećem pravilu:

Novi redak = Stari redak – (koeficijent stupca rezolucije starog retka)*(Novi redak rezolucije).

Na primjer, za z-string imamo:

Stari z-niz (-4 -6 0 0 0 0) -(-6)*Novi razrješavajući niz -(0 -6 0 0 -6 -120) =Novi z-niz (-4 0 0 0 6 120).

Za sljedeće tablice preračunavanje elemenata tablice radi se na sličan način, pa ga izostavljamo.

iteracija simpleks metode 1

							Stav

Razrješavanje stupca x 1, razrješavanje reda s 2, s 2 izlazi iz baze, x 1 ulazi u bazu. Na potpuno isti način dobivamo preostale simpleks tablice dok ne dobijemo tablicu sa svim pozitivnim koeficijentima u z-retku. Ovo je znak optimalne tablice.

iteracija simpleks metode 2

							Stav

Razrješavajući stupac s 3, razrješavajući red s 1, s 1 izlazi iz baze, s 3 ulazi u bazu.

iteracija simpleks metode 3

							Stav

U z-retku svi koeficijenti su nenegativni, pa je dobiveno optimalno rješenje x 1 = 24, x 2 = 16, z max = 192.

Simpleks metoda je iterativni proces usmjerenog rješavanja sustava jednadžbi u koracima, koji započinje referentnim rješenjem i, u potrazi za najboljom opcijom, kreće se duž kutnih točaka područja izvodljivog rješenja, poboljšavajući vrijednost funkcije cilja sve dok funkcija cilja dosegne optimalnu vrijednost.

Svrha usluge. Usluga je dizajnirana za online rješavanje problema linearnog programiranja (LPP) koristeći simpleks metodu u sljedećim notnim oblicima:

• u obliku simpleks tablice (metoda Jordanove transformacije); osnovni obrazac za snimanje;
• modificirana simpleks metoda; u obliku stupca; u linijskom obliku.

upute. Odaberite broj varijabli i broj redaka (broj ograničenja). Dobiveno rješenje sprema se u Word i Excel datoteku.

Broj varijabli 2 3 4 5 6 7 8 9 10
Broj redaka (broj ograničenja) 1 2 3 4 5 6 7 8 9 10

U ovom slučaju nemojte uzimati u obzir ograničenja poput x i ≥ 0. Ako u zadatku nema ograničenja za neki x i, tada se ZLP mora pretvoriti u KZLP ili koristiti ovu uslugu. Rješenje automatski određuje upotrebu M-metoda(simpleksna metoda s umjetnom osnovom) i dvostupanjska simpleks metoda.

Sljedeće se također koristi s ovim kalkulatorom:
Grafička metoda za rješavanje ZLP
Rješenje transportnog problema
Rješavanje igre matrice
Pomoću internetske usluge možete odrediti cijenu matrične igre (donje i gornje granice), provjeriti prisutnost sedlaste točke, pronaći rješenje za mješovitu strategiju pomoću sljedećih metoda: minimaks, simpleks metoda, grafička (geometrijska ) metoda, Brownova metoda.
Ekstrem funkcije dviju varijabli
Problemi dinamičkog programiranja
Podijelite 5 homogenih serija robe između tri tržišta kako biste ostvarili najveći prihod od njihove prodaje. Prihod od prodaje na svakom tržištu G(X) ovisi o broju prodanih serija proizvoda X i prikazan je u tablici.

Količina proizvoda X (u serijama)	Prihod G(X)
	1	2	3
0	0	0	0
1	28	30	32
2	41	42	45
3	50	55	48
4	62	64	60
5	76	76	72

Algoritam Simplex metode uključuje sljedeće korake:

1. Izrada prvog temeljnog plana. Prijelaz na kanonski oblik problema linearnog programiranja uvođenjem nenegativnih dodatnih bilančnih varijabli.
2. Provjera optimalnosti plana. Ako postoji barem jedan koeficijent indeksne linije manji od nule, tada plan nije optimalan i potrebno ga je poboljšati.
3. Određivanje vodećeg stupca i retka. Od negativnih koeficijenata indeksne linije odabire se najveći u apsolutnoj vrijednosti. Zatim se elementi stupca slobodnih članova simpleks tablice dijele na elemente istog predznaka vodećeg stupca.
4. Izrada novog referentnog plana. Prijelaz na novi plan provodi se kao rezultat ponovnog izračuna simpleksne tablice metodom Jordan-Gauss.

Ako je potrebno pronaći ekstrem funkcije cilja, tada govorimo o pronalaženju minimalne vrijednosti (F(x) → min, vidi primjer rješenja minimiziranja funkcije) i maksimalne vrijednosti ((F(x ) → max, vidi primjer rješenja za maksimiziranje funkcije)

Ekstremno rješenje postiže se na granici područja mogućih rješenja na jednom od vrhova kutnih točaka poligona ili na segmentu između dvije susjedne kutne točke.

Temeljni teorem linearnog programiranja. Ako funkcija cilja ZLP dosegne ekstremnu vrijednost u nekoj točki u području mogućih rješenja, tada uzima tu vrijednost u kutnoj točki. Ako funkcija cilja ZLP dosegne ekstremnu vrijednost u više od jedne kutne točke, tada uzima istu vrijednost u bilo kojoj od konveksnih linearnih kombinacija tih točaka.

Suština simpleks metode. Kretanje do optimalne točke provodi se pomicanjem od jedne kutne točke do susjedne, čime se približava i brže X opt. Takva shema za nabrajanje točaka, nazvana simpleks metoda, predložio R. Danzig.
Kutne točke karakteriziraju m osnovnih varijabli, pa se prijelaz iz jedne kutne točke u susjednu može ostvariti promjenom samo jedne osnovne varijable u bazi varijablom iz nebaze.
Implementacija simpleks metode, zbog različitih karakteristika i formulacija problema LP, ima različite modifikacije.

Izrada simpleks tablica nastavlja se sve dok se ne dobije optimalno rješenje. Kako možete koristiti simpleks tablicu da odredite da je rješenje problema linearnog programiranja optimalno?
Ako zadnji redak (vrijednosti funkcije cilja) ne sadrži negativne elemente, dakle, pronaći će optimalni plan.

Napomena 1. Ako je jedna od osnovnih varijabli jednaka nuli, tada je ekstremna točka koja odgovara takvom osnovnom rješenju degenerirana. Degeneracija se javlja kada postoji dvosmislenost u izboru linije vodilje. Možda uopće nećete primijetiti degeneraciju problema ako odaberete drugu liniju kao vodič. U slučaju dvosmislenosti treba odabrati redak s najnižim indeksom kako bi se izbjeglo ponavljanje.

Opaska 2. Neka su u nekoj ekstremnoj točki sve simpleks razlike nenegativne D k ³ 0 (k = 1..n+m), tj. dobije se optimalno rješenje i postoji A k - vektor bez baze za koji je D k = 0. Tada se maksimum postiže barem u dvije točke, tj. postoji alternativni optimum. Ako ovu varijablu x k uvedemo u bazu, vrijednost funkcije cilja se neće promijeniti.

Napomena 3. Rješenje dualnog problema nalazi se u posljednjoj simpleks tablici. Posljednjih m komponenti vektora simpleksnih razlika (u stupcima varijabli bilance) optimalno su rješenje dualnog problema. Vrijednosti objektivnih funkcija izravnog i dualnog problema u optimalnim točkama podudaraju se.

Napomena 4. Pri rješavanju problema minimizacije u bazu se uvodi vektor s najvećom pozitivnom simpleks razlikom. Zatim se primjenjuje isti algoritam kao i za problem maksimizacije.

Ako je naveden uvjet "Potrebno je da se sirovine tipa III potpuno utroše", tada je odgovarajući uvjet jednakost.