Je li vam se svidjelo? Dodaj u oznake

Rješavanje zadataka simpleks metodom: online primjeri

Zadatak 1. Tvrtka proizvodi kupaonske police u dvije veličine - A i B. Prodavač procjenjuje 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, koliko bi onda polica svake vrste trebalo proizvesti tjedno?

Zadatak 2. Riješite problem linearno programiranje simpleks metoda.

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 promjene 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 pri kojima rezultirajuća optimalan plan neće se promijeniti.

Zadatak 4. Riješite problem linearnog programiranja simpleks metoda:

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

Zadatak 6. Zadatak riješite simpleks metodom, smatrajući je početnom referentni plan, plan dat pod uvjetom:

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 za proizvode A i B, osiguravajući maksimalnu dobit od njihove prodaje.

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

Razmatran je primjer rješavanja zadatka simpleks metodom, kao i primjer rješenja dvostruki problem.

Stanje problema

Za prodaju tri grupe robe trgovačko poduzeće raspolaže s tri vrste ograničenih materijalno-novčanih sredstava u iznosu b 1 = 240, b 2 = 200, b 3 = 160 jedinica. U isto vrijeme, za prodaju 1 grupe robe za 1 tisuću rubalja. robnog prometa, resurs prve vrste troši se u količini a 11 = 2 jedinice, resurs druge vrste u količini a 21 = 4 jedinice, resurs treće vrste u količini a 31 = 4 jedinice. Za prodaju 2 i 3 grupe robe za 1 tisuću rubalja. promet se troši prema resursu prve vrste u iznosu a 12 = 3, a 13 = 6 jedinica, resursu druge vrste u količini a 22 = 2, a 23 = 4 jedinice, resursu treća vrsta u iznosu od a 32 = 6, a 33 = 8 jedinica . Dobit od prodaje tri grupe robe za 1 tisuću rubalja. promet je redom c 1 = 4, c 2 = 5, c 3 = 4 (tisuća rubalja). Utvrditi planirani obujam i strukturu trgovačkog prometa tako da dobit trgovačko poduzeće bio maksimum.

Na izravni problem planiranja prometa, rješava se simpleks metodom, sastaviti dvostruki problem linearno programiranje.
Instalirati konjugirani parovi varijabli izravni i dvostruki problemi.
Prema konjugiranim parovima varijabli, iz rješenja izravnog zadatka dobivamo rješenje dualnog problema, u kojem se proizvodi procjena resursa, potrošeno na prodaju robe.

Rješavanje problema simpleks metodom

Neka je x 1, x 2, x 3 broj prodane robe, u tisućama rubalja, 1, 2, 3 grupe, respektivno. Zatim matematički model zadatak ima oblik:

F = 4 x 1 + 5 x 2 + 4 x 3 ->maks

0)))(~)" title="delim(lbrace)(matrix(4)(1)((2x_1 + 3x_2 + 6x_3= 0)))(~)">!}

Rješavamo simpleks metodom.

Uvodimo dodatne varijable x 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0 da transformiramo nejednadžbe u jednakosti.

Uzmimo x 4 = 240 kao osnovu; x 5 = 200; x 6 = 160.

Unosimo podatke u simplex tablica

Jednostavna tablica br. 1

Ciljna funkcija:

0 240 + 0 200 + 0 160 = 0

Procjene izračunavamo pomoću formule:

Δ 1 = 0 2 + 0 4 + 0 4 - 4 = - 4
Δ 2 = 0 3 + 0 2 + 0 6 - 5 = - 5
Δ 3 = 0 6 + 0 4 + 0 8 - 4 = - 4
Δ 4 = 0 1 + 0 0 + 0 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 0 0 - 0 = 0
Δ 6 = 0 0 + 0 0 + 0 1 - 0 = 0

Budući da postoje negativne procjene, plan nije optimalan. Najniža ocjena:

Varijablu x 2 uvodimo u bazu.

Definiramo varijablu koja proizlazi iz baze. Da bismo to učinili, nalazimo najmanji nenegativan omjer za x2 stupac.

= 26.667

Najmanji nenegativan: Q 3 = 26,667. Varijablu x 6 izvodimo iz baze

Treću liniju podijelite sa 6.
Od 1. retka oduzmite 3. redak, pomnoženo s 3
Od 2. retka oduzmite 3. redak, pomnožen s 2

Računamo:

Dobivamo novi stol:

Jednostavna tablica br. 2

Ciljna funkcija:

0 160 + 0 440/3 + 5 80/3 = 400/3

Procjene izračunavamo pomoću formule:

Δ 1 = 0 0 + 0 8/3 + 5 2/3 - 4 = - 2/3
Δ 2 = 0 0 + 0 0 + 5 1 - 5 = 0
Δ 3 = 0 2 + 0 4/3 + 5 4/3 - 4 = 8/3
Δ 4 = 0 1 + 0 0 + 5 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 5 0 - 0 = 0
Δ 6 = 0 (-1)/2 + 0 (-1)/3 + 5 1/6 - 0 = 5/6

Budući da postoji negativna procjena Δ 1 = - 2/3, plan nije optimalan.

U bazu uvodimo varijablu x 1.

Definiramo varijablu koja proizlazi iz baze. Da bismo to učinili, pronalazimo najmanji nenegativan omjer za stupac x 1.

Najmanji nenegativan: Q 3 = 40. Varijablu x 2 izvodimo iz baze

Treću liniju podijelite s 2/3.
Od 2. retka oduzmite 3. redak, pomnožen s 8/3

Računamo:

Dobivamo novu tablicu:

Jednostavna tablica br. 3

Ciljna funkcija:

0 160 + 0 40 + 4 40 = 160

Procjene izračunavamo pomoću formule:

Δ 1 = 0 0 + 0 0 + 4 1 - 4 = 0
Δ 2 = 0 0 + 0 (-4) + 4 3/2 - 5 = 1
Δ 3 = 0 2 + 0 (-4) + 4 2 - 4 = 4
Δ 4 = 0 1 + 0 0 + 4 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 4 0 - 0 = 0
Δ 6 = 0 (-1)/2 + 0 (-1) + 4 1/4 - 0 = 1

Budući da nema negativnih ocjena, plan je optimalan.

Rješenje problema:

Odgovor

x 1 = 40; x2 = 0; x 3 = 0; x 4 = 160; x 5 = 40; x6 = 0; F max = 160

To jest, potrebno je prodati prvu vrstu robe u iznosu od 40 tisuća rubalja. Proizvode tipa 2 i 3 nije potrebno prodavati. Istovremeno maksimalan profit bit će F max = 160 tisuća rubalja.

Rješenje dualnog problema

Dualni problem ima oblik:

Z = 240 y 1 + 200 y 2 + 160 y 3 -> min

Title="delim(lbrace)(matrix(4)(1)((2y_1 + 4y_2 + 4y_3>=4) (3y_1 + 2y_2 + 6y_3>=5) (6y_1 + 4y_2 + 8y_3>=4) (y_1, y_2, y_3>= 0)))(~)">!}

Uvodimo dodatne varijable y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0 da transformiramo nejednadžbe u jednakosti.

Konjugirani parovi varijabli izravnog i dualnog problema imaju oblik:

Iz posljednje simpleks tablice br. 3 izravnog problema nalazimo rješenje dualnog problema:

Z min = F max = 160;
y 1 = Δ 4 = 0; y 2 = Δ 5 = 0; y 3 = Δ 6 = 1; y 4 = Δ 1 = 0; y 5 = Δ 2 = 1; y 6 = Δ 3 = 4;

. Algoritam Simplex metode

Primjer 5.1. Simpleks metodom riješite sljedeći problem linearnog programiranja:

Otopina:

ja ponavljanje:

x3, x4, x5, x6 x1,x2. Izrazimo osnovne varijable u terminima slobodnih:

Svedimo ciljnu funkciju na sljedeći pogled:

Na temelju dobivenog problema formirat ćemo početnu simpleks tablicu:

Tablica 5.3

Izvorni simplex stol

				Evaluativni odnosi

Prema definiciji osnovnog rješenja slobodne varijable su jednake nuli, a vrijednosti osnovnih varijabli jednake su odgovarajućim vrijednostima slobodnih brojeva, tj.

Faza 3: provjera kompatibilnosti sustava ograničenja PAP.

U ovoj iteraciji (u tablici 5.3), znak nekonzistentnosti sustava ograničenja (znak 1) nije identificiran (tj. ne postoji linija s negativnim slobodnim brojem (osim linije funkcije cilja) u kojoj ne bi bilo biti barem jedan negativan element (tj. negativan koeficijent za slobodnu varijablu)).

U ovoj iteraciji (u tablici 5.3) nije identificiran predznak neograničenosti funkcije cilja (znak 2) (tj. ne postoji stupac s negativnim elementom u retku funkcije cilja (osim stupca slobodnih brojeva). ) u kojem ne bi postojao barem jedan pozitivan element) .

Budući da pronađeno osnovno rješenje ne sadrži negativne komponente, ono je dopušteno.

Faza 6: provjera optimalnosti.

Nađeno osnovno rješenje nije optimalno, jer prema kriteriju optimalnosti (predznak 4) ne bi trebalo biti negativnih elemenata u liniji funkcije cilja ( besplatan broj ova se linija ne uzima u obzir pri razmatranju ove karakteristike). Stoga, prema algoritmu simpleks metode, prelazimo na fazu 8.

Budući da je pronađeno osnovno rješenje dopustivo, razlučujući stupac ćemo tražiti prema sljedećoj shemi: određujemo stupce s negativnim elementima u retku funkcije cilja (osim stupca slobodnih brojeva). Prema tablici 5.3 postoje dva takva stupca: stupac " x1" i stupac " x2" Iz takvih stupaca odabire se onaj koji sadrži najmanji element u retku ciljne funkcije. Ona će biti popustljiva. Stupac " x2" sadrži najmanji element (–3) u usporedbi sa stupcem " x1

Da bismo odredili rezolirajuću liniju, nalazimo pozitivne procijenjene omjere slobodnih brojeva prema elementima rezolirajućeg stupca; crta koja odgovara najmanjem pozitivnom omjeru procjene se prihvaća kao riješena.

Tablica 5.4

Izvorni simplex stol

U tablici 5.4 najmanji pozitivni evaluacijski odnos odgovara liniji " x5“, dakle, to će biti popustljivo.

Element koji se nalazi na sjecištu stupca za omogućavanje i retka za omogućavanje prihvaća se kao omogućavajući. U našem primjeru, to je element koji se nalazi na sjecištu linije " x5" i stupci " x2».

Element razrješenja prikazuje jednu bazu i jednu slobodnu varijablu koje se moraju zamijeniti u simpleks tablici da bi se prešlo na novo "poboljšano" osnovno rješenje. U u ovom slučaju to su varijable x5 I x2, u novoj simpleks tablici (tablica 5.5) ih mijenjamo.

9.1. Transformacija razlučnog elementa.

Element rezolucije tablice 5.4 pretvara se na sljedeći način:

Dobiveni rezultat unosimo u sličnu ćeliju u tablici 5.5.

9.2. Pretvorba niza rezolucije.

Podijelimo elemente retka razlučivanja tablice 5.4 s elementom razrješenja ove simpleks tablice, rezultati se uklapaju u slične ćelije nove simpleks tablice (tablica 5.5). Transformacije elemenata niza rezolucije dane su u tablici 5.5.

9.3. Pretvorba stupca rezolucije.

Podijelimo elemente stupca razlučivosti tablice 5.4 elementom razlučivosti ove simpleks tablice, a rezultat je uzet iz suprotnog predznaka. Dobiveni rezultati uklapaju se u slične ćelije nove simpleks tablice (tablica 5.5). Transformacije elemenata stupca rezolucije dane su u tablici 5.5.

9.4. Transformacija preostalih elemenata simpleks tablice.

Transformacija preostalih elemenata simpleks tablice (tj. elemenata koji se ne nalaze u retku razrješenja i stupcu razrješenja) provodi se prema pravilu "pravokutnika".

Na primjer, razmotrite transformaciju elementa koji se nalazi na sjecištu linije " x3" i stupaca "", uvjetno ćemo ga označiti " x3" U tablici 5.4 mentalno crtamo pravokutnik čiji se jedan vrh nalazi u ćeliji čiju vrijednost transformiramo (tj. u ćeliji “ x3"), a drugi (dijagonalni vrh) je u ćeliji s razlučnim elementom. Ostala dva vrha (druge dijagonale) jednoznačno su određena. Zatim transformirana vrijednost ćelije " x3" bit će jednaka prethodnoj vrijednosti ove ćelije minus razlomak u čijem je nazivniku razlučni element (iz tablice 5.4), a u brojniku umnožak druga dva neiskorištena vrha, tj.:

« x3»: .

Vrijednosti ostalih ćelija pretvaraju se na sličan način:

« x3 x1»: ;

« x4»: ;

« x4 x1»: ;

« x6»: ;

« x6 x1»: ;

«»: ;

« x1»: .

Kao rezultat ovih transformacija dobili smo novu simplex tablica(Tablica 5.5).

II ponavljanje:

Faza 1: izrada simpleks tablice.

Tablica 5.5

Simplex tablicaII ponavljanja

				Procijenjeno odnos

Faza 2: određivanje osnovne otopine.

Kao rezultat simpleks transformacija dobiveno je novo bazično rješenje (tablica 5.5):

Kao što vidite, kod ovog osnovnog rješenja vrijednost funkcije cilja = 15, što je više nego kod prethodnog osnovnog rješenja.

Nije utvrđena nedosljednost sustava ograničenja u skladu sa značajkom 1 u tablici 5.5.

Faza 4: provjera ograničenosti funkcije cilja.

Neograničenost funkcije cilja u skladu s kriterijem 2 u tablici 5.5 nije otkrivena.

5. faza: provjera prihvatljivosti pronađenog temeljnog rješenja.

Pronađeno osnovno rješenje u skladu s kriterijem 4 nije optimalno, jer linija funkcije cilja simpleks tablice (tablica 5.5) sadrži negativan element: –2 (slobodni broj ove linije nije uzet u obzir pri razmatranju ove karakteristika). Stoga prelazimo na fazu 8.

Faza 8: određivanje razlučnog elementa.

8.1. Definicija stupca rezolucije.

Nađeno osnovno rješenje je prihvatljivo, određuju se stupci s negativnim elementima u retku funkcije cilja (osim stupca slobodnih brojeva). Prema tablici 5.5 postoji samo jedan takav stupac: " x1" Stoga ga prihvaćamo kao dopušteno.

8.2. Definicija niza za uključivanje.

Prema dobivenim vrijednostima pozitivnih evaluacijskih odnosa u tablici 5.6, minimalna je relacija koja odgovara liniji “ x3" Stoga ga prihvaćamo kao dopušteno.

Tablica 5.6

Simplex tablicaII ponavljanja

				Procijenjeno odnos
				3/1=3 – min

Faza 9: transformacija simpleks tablice.

Transformacije simpleks tablice (tablica 5.6) izvode se na isti način kao u prethodnoj iteraciji. Rezultati transformacija elemenata simpleks tablice dani su u tablici 5.7.

III ponavljanje

Na temelju rezultata simpleks transformacija prethodne iteracije sastavljamo novu simpleks tablicu:

Tablica 5.7

Simplex tablicaIII ponavljanja

				Procijenjeno odnos

Faza 2: određivanje osnovne otopine.

Kao rezultat simpleks transformacija dobiveno je novo osnovno rješenje (tablica 5.7):

Faza 3: provjera kompatibilnosti sustava ograničenja.

Nije utvrđena nedosljednost sustava ograničenja u skladu sa značajkom 1 u tablici 5.7.

Faza 4: provjera ograničenosti funkcije cilja.

Neograničenost funkcije cilja u skladu s kriterijem 2 u tablici 5.7 nije otkrivena.

5. faza: provjera prihvatljivosti pronađenog temeljnog rješenja.

Nađeno osnovno rješenje prema kriteriju 3 je prihvatljivo jer ne sadrži negativne komponente.

Faza 6: provjera optimalnosti pronađenog osnovnog rješenja.

Pronađeno osnovno rješenje u skladu s kriterijem 4 nije optimalno, budući da linija funkcije cilja simpleks tablice (tablica 5.7) sadrži negativan element: –3 (slobodni broj ove linije nije uzet u obzir pri razmatranju ovoga karakteristika). Stoga prelazimo na fazu 8.

Faza 8: određivanje razlučnog elementa.

8.1. Definicija stupca rezolucije.

Nađeno osnovno rješenje je prihvatljivo, određuju se stupci s negativnim elementima u retku funkcije cilja (osim stupca slobodnih brojeva). Prema tablici 5.7 postoji samo jedan takav stupac: “ x5" Stoga ga prihvaćamo kao dopušteno.

8.2. Definicija niza za uključivanje.

Prema dobivenim vrijednostima pozitivnih evaluacijskih odnosa u tablici 5.8, minimalna je relacija koja odgovara liniji “ x4" Stoga ga prihvaćamo kao dopušteno.

Tablica 5.8

Simplex tablicaIII ponavljanja

				Procijenjeno odnos
				5/5=1 – min

Faza 9: transformacija simpleks tablice.

Transformacije simpleks tablice (tablica 5.8) izvode se na isti način kao u prethodnoj iteraciji. Rezultati transformacija elemenata simpleks tablice dani su u tablici 5.9.

IV ponavljanje

Faza 1: konstrukcija nove simpleks tablice.

Na temelju rezultata simpleks transformacija prethodne iteracije sastavljamo novu simpleks tablicu:

Tablica 5.9

Simplex tablicaIV ponavljanja

				Procijenjeno odnos
			–(–3/5)=3/5
			–(1/5)=–1/5
			–(9/5)=–9/5
			–(–3/5)=3/5

Faza 2: određivanje osnovne otopine.

Kao rezultat simpleksnih transformacija, dobiveno je novo osnovno rješenje prema tablici 5.9, rješenje je sljedeće:

Faza 3: provjera kompatibilnosti sustava ograničenja.

Nije utvrđena nedosljednost sustava ograničenja u skladu sa značajkom 1 u tablici 5.9.

Faza 4: provjera ograničenosti funkcije cilja.

Neograničenost funkcije cilja u skladu s kriterijem 2 u tablici 5.9 nije otkrivena.

5. faza: provjera prihvatljivosti pronađenog temeljnog rješenja.

Nađeno osnovno rješenje prema kriteriju 3 je prihvatljivo jer ne sadrži negativne komponente.

Faza 6: provjera optimalnosti pronađenog osnovnog rješenja.

Pronađeno osnovno rješenje u skladu sa značajkom 4 je optimalno, budući da nema negativnih elemenata u retku funkcije cilja simpleks tablice (tablica 5.9) (slobodni broj ovog retka nije uzet u obzir pri razmatranju ovog obilježja) .

Faza 7: provjera alternativnosti rješenja.

Nađeno rješenje je jedinstveno, jer linija funkcije cilja (tablica 5.9) ne sadrži nulti elementi(slobodni broj ove linije ne uzima se u obzir pri razmatranju ove karakteristike).

Odgovor: optimalna vrijednost funkcija cilja razmatranog problema =24, što se postiže pri.

Primjer 5.2. Riješite gornji problem linearnog programiranja uz uvjet da je funkcija cilja minimizirana:

Otopina:

ja ponavljanje:

Faza 1: formiranje početne simpleks tablice.

Izvorni problem linearno programiranje navedeno je u standardni obrazac. Dovedimo to do kanonski oblik uvođenjem u svako od ograničenja nejednakosti dodatne ne-negativne varijable, tj.

U dobivenom sustavu jednadžbi uzimamo kao dopuštene (osnovne) varijable x3, x4, x5, x6, tada će slobodne varijable biti x1,x2. Izrazimo osnovne varijable preko slobodnih.

Simpleks metoda je iterativni proces usmjerenog rješavanja sustava jednadžbi korak po korak, koji počinje s referentnim rješenjem iu potrazi za najbolja opcija pomiče se duž kutnih točaka područja izvodljivog rješenja, poboljšavajući vrijednost funkcije cilja sve dok funkcija cilja ne dosegne optimalnu vrijednost.

Svrha usluge. Usluga je namijenjena online rješenja Problemi linearnog programiranja (LPP) korištenjem simpleks metode u sljedeći oblici unosi:

• u obliku simpleks tablice (metoda Jordanove transformacije); osnovni oblik zapisi;
• modificirana simpleks metoda; u obliku stupca; u linijskom obliku.

upute. Odaberite broj varijabli i broj redaka (broj ograničenja). Dobivena otopina se čuva u Word datoteka i Excel.

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. Prilikom rješavanja automatski se određuje korištenje 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 matrice igre
Korištenje usluge u mrežni način rada 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 tako da dobijete maksimalan 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. Idi na kanonski oblik probleme 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 apsolutna vrijednost. 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 o potrazi minimalna vrijednost(F(x) → min , vidi primjer rješavanja minimizacije funkcije) i maksimalna vrijednost((F(x) → max , vidi primjer rješavanja maksimizacije 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 linearna kombinacija ove točke.

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 postići promjenom samo jedne osnovne varijable u bazi u varijablu iz nebaze.
Primjena simpleks metode na snazi razne značajke i izjave o problemima, LP ima različite modifikacije.

Izrada simpleks tablica nastavlja se 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 takav A k - vektor bez baze za koji je D k = 0. Tada se maksimum postiže pomoću najmanje 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.

Ova metoda je metoda svrhovitog nabrajanja referentnih rješenja problema linearnog programiranja. Omogućuje, u konačnom broju koraka, pronalaženje optimalnog rješenja ili utvrđivanje nepostojanja optimalnog rješenja.

Glavni sadržaj simpleks metode je sljedeći:

1. Navedite metodu za pronalaženje optimalnog referentnog rješenja
2. Navedite način prijelaza s jednog referentnog rješenja na drugo, pri čemu će vrijednost funkcije cilja biti bliža optimalnoj, tj. navesti način poboljšanja referentnog rješenja
3. Postavite kriterije koji vam omogućuju da trenutno prestanete tražiti rješenja za podršku na optimalnom rješenju ili izvučete zaključak o nepostojanju optimalnog rješenja.

Algoritam simpleks metode za rješavanje problema linearnog programiranja

Kako biste riješili problem koristeći simplex metodu, morate učiniti sljedeće:

1. Dovedite problem u kanonski oblik
2. Pronađite početno rješenje potpore s “jediničnom osnovom” (ako ne postoji rješenje potpore, onda problem nema rješenje zbog nekompatibilnosti sustava ograničenja)
3. Izračunajte procjene vektorskih dekompozicija na temelju referentnog rješenja i ispunite tablicu simpleks metode
4. Ako je kriterij jedinstvenosti optimalnog rješenja zadovoljen, tada rješenje problema završava
5. Ako je ispunjen uvjet postojanja skupa optimalnih rješenja, tada se sva optimalna rješenja nalaze jednostavnim nabrajanjem

Primjer rješavanja zadatka simpleks metodom

Primjer 26.1

Zadatak riješite simpleks metodom:

Otopina:

Problem dovodimo u kanonski oblik.

U tu svrhu u lijeva strana Za prvo ograničenje nejednakosti uvodimo dodatnu varijablu x 6 s koeficijentom +1. Varijabla x 6 uključena je u funkciju cilja s koeficijentom nula (tj. nije uključena).

Dobivamo:

Pronalazimo početno rješenje za podršku. Da bismo to učinili, izjednačavamo slobodne (nerazriješene) varijable s nulom x1 = x2 = x3 = 0.

Dobivamo referentno rješenje X1 = (0,0,0,24,30,6) s jediničnom osnovom B1 = (A4, A5, A6).

Računamo procjene vektorskih dekompozicija uvjetima na temelju referentne otopine prema formuli:

Δ k = C b X k - c k

• C b = (c 1, c 2, ..., c m) - vektor koeficijenata funkcije cilja za osnovne varijable
• X k = (x 1k, x 2k, ..., x mk) - vektor proširenja odgovarajućeg vektora A k prema bazi referentnog rješenja
• C k je koeficijent funkcije cilja za varijablu x k.

Procjene vektora uključenih u bazu uvijek su jednake nuli. Referentno rješenje, koeficijenti proširenja i procjene proširenja vektora uvjeta na temelju referentnog rješenja zapisani su u simplex tablica:

Na vrhu tablice, radi lakšeg izračunavanja procjena, ispisani su koeficijenti funkcije cilja. U prvi stupac "B" upisuju se vektori koji ulaze u bazu referentnog rješenja. Redoslijed kojim su ti vektori zapisani odgovara broju dopuštenih nepoznanica u jednadžbama ograničenja. U drugom stupcu tablice "C b" istim redom ispisani su koeficijenti funkcije cilja za osnovne varijable. Na ispravan položaj Koeficijenti funkcije cilja u stupcu "C b" procjene jediničnih vektora uključenih u bazu uvijek su jednaki nuli.

U zadnji redak tablice s procjenama Δ k u stupcu "A 0" upisuju se vrijednosti funkcije cilja na referentnom rješenju Z(X 1).

Početno rješenje potpore nije optimalno jer su u problemu maksimuma procjene Δ 1 = -2, Δ 3 = -9 za vektore A 1 i A 3 negativne.

Prema teoremu o poboljšanju rješenja potpore, ako u problemu maksimuma barem jedan vektor ima negativnu procjenu, tada se može pronaći novo rješenje potpore na kojem će vrijednost funkcije cilja biti veća.

Odredimo koji će od dva vektora dovesti do većeg povećanja funkcije cilja.

Prirast funkcije cilja nalazi se po formuli: .

Izračunavamo vrijednosti parametra θ 01 za prvi i treći stupac pomoću formule:

Dobivamo θ 01 = 6 za l = 1, θ 03 = 3 za l = 1 (tablica 26.1).

Prirast funkcije cilja nalazimo kada u bazu uvedemo prvi vektor ΔZ 1 = - 6*(- 2) = 12, a treći vektor ΔZ 3 = - 3*(- 9) = 27.

Slijedom toga, za brže približavanje optimalnom rješenju potrebno je umjesto prvog vektora baze A6 uvesti vektor A3 u bazu referentnog rješenja, jer se minimum parametra θ 03 postiže u prvom redu ( l = 1).

Provodimo Jordanovu transformaciju s elementom X13 = 2, dobivamo drugo referentno rješenje X2 = (0,0,3,21,42,0) s bazom B2 = (A3, A4, A5). (Tablica 26.2)

Ovo rješenje nije optimalno jer vektor A2 ima negativnu procjenu Δ2 = - 6. Za poboljšanje rješenja potrebno je uvesti vektor A2 u bazu referentnog rješenja.

Određujemo broj vektora izvedenog iz baze. Da bismo to učinili, izračunavamo parametar θ 02 za drugi stupac, on je jednak 7 za l = 2. Posljedično, izvodimo drugi bazni vektor A4 iz baze. Provodimo Jordanovu transformaciju s elementom x 22 = 3, dobivamo treće referentno rješenje X3 = (0,7,10,0,63,0) B2 = (A3, A2, A5) (tablica 26.3).

Ovo rješenje je jedino optimalno, jer su za sve vektore koji nisu uključeni u bazu ocjene pozitivne

Δ 1 = 7/2, Δ 4 = 2, Δ 6 = 7/2.

Odgovor: max Z(X) = 201 kod X = (0,7, 10, 0,63).

Metoda linearnog programiranja u ekonomskoj analizi

Metoda linearnog programiranja omogućuje opravdanje najoptimalnijeg ekonomska odluka u uvjetima oštrih ograničenja vezanih uz resurse koji se koriste u proizvodnji (dugotrajna imovina, materijali, radna sredstva). Korištenje ove metode u ekonomskoj analizi omogućuje rješavanje problema koji se uglavnom odnose na planiranje aktivnosti organizacije. Ova metoda pomaže odrediti optimalne izlazne razine, kao i upute za većinu učinkovitu upotrebu proizvodnih resursa dostupnih organizaciji.

Ovom metodom rješavaju se tzv. ekstremni problemi koji se sastoje u pronalaženju ekstremnih vrijednosti, odnosno maksimuma i minimuma funkcija varijable.

Ovo razdoblje temelji se na rješavanju sustava linearnih jednadžbi u slučajevima kada su analizirani ekonomski fenomeni povezani linearno, strogo funkcionalna ovisnost. Metoda linearnog programiranja koristi se za analizu varijabli u prisutnosti određenih ograničavajućih čimbenika.

Vrlo često rješenje je tzv transportni problem metodom linearnog programiranja. Sadržaj ovog zadatka je minimiziranje troškova koji nastaju u vezi s radom vozila pod postojećim ograničenjima u pogledu broja vozila, njihove nosivosti, trajanja njihovog rada, ako postoji potreba za održavanjem maksimalna količina kupaca.

Osim ovoga, ovu metodu naširoko se koristi u rješavanju problema raspoređivanja. Ovaj zadatak sastoji se od takve raspodjele radnog vremena za osoblje određene organizacije koja bi bila najprihvatljivija kako za članove ovog osoblja tako i za klijente organizacije.

Ovaj zadatak je maksimizirati broj usluženih klijenata u uvjetima ograničenja broja raspoloživog osoblja, kao i fonda radnog vremena.

Stoga je metoda linearnog programiranja prilično česta u analizi postavljanja i korištenja. razne vrste resursa, kao iu procesu planiranja i predviđanja aktivnosti organizacija.

Ipak, matematičko programiranje može se primijeniti i na one ekonomske pojave čiji odnos nije linearan. U tu svrhu mogu se koristiti metode nelinearnog, dinamičkog i konveksnog programiranja.

Nelinearno programiranje oslanja se na nelinearnu prirodu funkcije cilja ili ograničenja, ili oboje. Oblici funkcije cilja i ograničenja nejednakosti u ovim uvjetima mogu biti različiti.

Nelinearno programiranje koristi se u ekonomskoj analizi, posebno kada se uspostavlja odnos između pokazatelja koji izražavaju učinkovitost aktivnosti organizacije i opsega ove aktivnosti, strukture troškova proizvodnje, tržišnih uvjeta itd.

Dinamičko programiranje temelji se na konstruiranju stabla odlučivanja. Svaki sloj ovog stabla služi kao pozornica za određivanje posljedica prijašnja odluka i eliminirati neučinkovite opcije za ovo rješenje. dakle, dinamičko programiranje ima višestepenu, višefaznu prirodu. Ova vrsta programiranja koristi se u ekonomskoj analizi za pronalaženje optimalne opcije razvoj organizacije sada i u budućnosti.

Konveksno programiranje je vrsta nelinearnog programiranja. Ova vrsta programiranja izražava nelinearnu prirodu odnosa između rezultata aktivnosti organizacije i njezinih troškova. Konveksno (aka konkavno) programiranje analizira konveksno objektivne funkcije i konveksni sustavi ograničenja (točke prihvatljive vrijednosti). Konveksno programiranje koristi se u analizi gospodarskih aktivnosti s ciljem minimiziranja troškova, a konkavno programiranje s ciljem maksimiziranja prihoda uz postojeća ograničenja na djelovanje čimbenika koji suprotno utječu na analizirane pokazatelje. Posljedično, s vrstama programiranja koje se razmatraju, konveksne ciljne funkcije su minimizirane, a konkavne ciljne funkcije su maksimizirane.