Razmotrimo univerzalna metoda rješenja kanonskog problema linearno programiranje

S n varijable i m ograničenja jednakosti, poznata kao simpleks metoda.

Skup planova za kanonski problem je konveksni poliedarski skup s konačnim brojem kutnih točaka. A ako ovaj problem ima optimalno rješenje, onda je ono postignuto barem u jednoj kutnoj točki.

Bilo kojoj kutnoj točki pridružuje se osnovni plan problema u kojem su varijable jednake nuli, a preostale varijable odgovaraju linearno neovisnim stupcima matrice uvjeta. Ovi linearno neovisni stupci tvore nesingularnu baznu matricu.

Ponavljanje preko svih kutnih točaka je računski skupo i stoga neučinkovito. Godine 1947. J. Danzig je predložio uredan postupak za nabrajanje kutnih točaka, u kojem je za optimalno rješenje dovoljno ispitati samo mali dio njih. Ovaj postupak se zove simpleks metoda.

J. Dantzig je predložio zamjenu samo jednog vektora u baznoj matrici kada se kreće od jedne krajnje točke do druge. To znači da tijekom takvog prijelaza moramo isključiti jednu od osnovnih varijabli - učiniti je nebazičnom ( jednaka nuli), a na njeno mjesto uvesti novu varijablu među nebazičnim (nula) - učiniti je bazičnom (pozitivnom).

Ispada da geometrijski takva zamjena dovodi do prijelaza s jedne kutne točke na susjednu (susjednu) povezanu s prethodna točka zajednički rub.

Od svih susjednih točaka odabire se ona u kojoj funkcija cilja najviše raste. Budući da je broj kutnih točaka konačan, kroz konačan broj prijelaza vrh sa najveća vrijednost funkcija cilja, odnosno neograničenost funkcije cilja bit će uspostavljena na neograničenom skupu planova.

Opća shema simpleks metode sastoji se od sljedećih glavnih koraka.

· korak 0. Određivanje početne baze i pripadajuće početne kutne točke (baze).

· korak 1. Provjera optimalnosti trenutne osnovne linije . Ako je kriterij optimalnosti zadovoljen, Da plan je optimalan i rješenje je potpuno. Inače idite na korak 2.

· korak 2. Pronalaženje varijable uvedeno u osnovne. (Iz uvjeta povećanja funkcije cilja).

· korak 3. Pronalaženje varijable isključene iz osnovnih varijabli (Iz uvjeta očuvanja ograničenja problema).

· korak 4 . Pronalaženje koordinata nove osnovne crte (susjedna kutna točka). Idite na 1. korak.

Ponovljeni koraci 1-4 čine jednu iteraciju simpleks metode.

Iz ovog dijagrama slijedi da, prvo, da biste započeli simpleks metodu, morate imati neku vrstu kutne točke - početni osnovni plan, i drugo, morate biti u mogućnosti ispitati trenutnu kutnu točku radi optimalnosti bez izračunavanja svih susjednih vrhovi. Ovi problemi se lako rješavaju ako kanonski LP problem ima neki poseban oblik.

Definicija. Reći ćemo da kanonski LP problem ima “preferirani oblik” ako

1. desne strane jednadžbi, .

2. matrica uvjeta sadrži jediničnu submatricu veličine

Drugim riječima, u bilo kojoj jednadžbi postoji varijabla s koeficijentom jednakim jedan, koji je odsutan u drugim jednadžbama. Prvi uvjet nije težak, jer je u slučaju negativne desne strane neke jednadžbe dovoljno pomnožiti s (-1). U problemu preferencijalnog tipa, pronalaženje početne osnovne linije je vrlo jednostavno.

Primjer 2.1.

Matrica uvjeta A a vektor desnih strana ograničenja b izgledati kao

i ciljni vektor c = (1, -3, 0, 4, 2).

Jedna bazna matrica je odmah očita: s jediničnim vektorima uvjeta.

Stoga, birajući kao osnovne varijable x 1 , x 3 ,x 5 , i stavljanje u sustav jednadžbi x 2 = x 4 = 0 (neosnovne varijable) , nalazimo odmah x 1 = 10,x 3 = 20,x 5 = 8, dakle početna osnovna linija x 0 = (10, 0, 20, 0, 8). Vidimo da su vrijednosti osnovnih varijabli jednake desnim stranama ograničenja. Iz ovoga je jasno da desne strane moraju biti pozitivne b ja .

U budućnosti ćemo osnovne varijable kombinirati u vektor x B.

Dakle, u kanonski problem preferiranog oblika, podmatrica identiteta se uzima kao početna bazna matrica A B = E, a odgovarajuće bazne varijable jednake su desnim stranama ograničenja:

x B = b.

Za osnovni plan ove vrste može se formulirati kriterij optimalnosti koji je dovoljno jednostavan za testiranje. Predstavimo količine

? j = < с B , A j > - c j , j = 1,...,n,(2.1)

Gdje S B- vektor koeficijenata funkcije cilja za osnovne varijable x B , A j -j- th stupac matrice uvjeta, c j -j- koeficijent funkcije cilja. Razlike ? j nazivaju se simpleks razlike ili simpleks procjene.

Kriterij optimalnosti temeljnog plana. Ako za osnovni plan s jedinicom osnovna matrica sve simpleks procjene nisu negativne, onda je ovaj plan optimalan.

Primijenimo ovaj kriterij za provjeru optimalnosti osnovnog plana x 0 = (10, 0, 20, 0, 8) iz primjera 2.1.

Budući da u tom pogledu vektor osnovnih varijabli x B =(x 1 , x 3 ,x 5 ), To S B = (c 1 , c 3 ,c 5 ) = (1, 0, 2).

Stoga,

? 1 = < с B , A 1 > - c 1 = 1 1 + 0 0 + 2 0 - 1= 0,

2 = < сБ, A2 >- c2 = 1 3 + 0 1 + 2 2 - (-3) = 10,

? 3 = < с B , A 3 > - c 3 = 1 0 + 0 1 + 2 0 - 0= 0,

? 4 = < с B , A 4 > - c 4 = 1 (-1) + 0 5 + 2 1 - 4= -3,

? 5 = < с B , A 5 > - c 5 = 1 0 + 0 0 + 2 1 - 2= 0.

Od procjene ? 4 < 0, то базисный план x 0 nije optimalno. Imajte na umu da su simpleks procjene koje odgovaraju osnovnim varijablama uvijek jednake nuli, pa je dovoljno provjeriti samo nebazične procjene.

Simpleks metoda sastoji se od pronalaženja i testiranja vrha (kuta) koji je rješenje problema LP. U svakoj fazi, metoda odabire vrh i njegove odgovarajuće varijable, koje osiguravaju kretanje na minimum (maksimum) s najveća brzina. Odabrana varijabla zamjenjuje drugu, najrestriktivniju. Simpleks metoda također vam omogućuje da odredite postoji li rješenje. Algoritam koji implementira simpleks metodu može se napisati kao:

Korak 1. Određuje se određeni vrh u ODR-u koji odgovara osnovnim dopustivim rješenjima (varijablama) dobivenim izdvajanjem iz matrice T- linearni nezavisne kolone i postavljanje svih ostalih varijabli koje odgovaraju drugim stupcima matrice na nulu.

Korak 2. Odabrano od svih mogućih preostalih p - t bridovi koji odgovaraju nebazičnim varijablama, brid (varijabla) koji, krećući se duž njega, dovodi do najbržeg pada funkcije cilja.

3. korak To je kao da se izvodi pomak od početnog vrha uz odabrani brid do drugog vrha, čime se dobiva novo rješenje koje ima manju CF vrijednost. Novi vrh se formira zamjenom bazne varijable (brid) novom baznom varijablom (brid).

Stupci i elementi vektora obično su poredani i zapisani u obliku simpleks tablice čije će formiranje biti prikazano u nastavku.

Simpleks metoda rješava problem LP u standardna forma.

Minimizirati (maksimizirati) funkciju pod uvjetima x > 0; Sjekira = b.

Matrica A je realna i ima dimenziju T x "i rang T.

Formulirani problem LP može se napisati iu obliku

Na temelju snimanja LP problema u obliku (8L) možemo reći da je proširena matrica

dimenzije (t + 1) (n + 2) odgovara rješenjima[x/] t.

Predstavimo matricu A kao skup stupaca

Budući da matrica A ima rang T, onda će biti T linearno neovisni stupci matrice A, na primjer (a V1 ,...,a V/i. Razmotrimo vektor x° > 0, takav da je sav p - t elementi su 0 i Ax° = b. Neka to budu elementi s brojevima..., u M . Pretpostavimo također da položaj aw linearno neovisnih stupaca matrice A odgovara položaju elemenata koji nisu nula u vektorima 0. Geometrijski, prema izjavi 3 § 7.6, to znači da je x° vrh (kut) ODR-a i, dodatno, zadovoljava zadane uvjete. Ovo rješenje se zove dopušteno osnovno rješenje. Kutovi dopustivog skupa su dopuštena temeljna rješenja.

Podsjetimo se da skup osnovnih rješenja sadrži sve informacije potrebne za optimalno rješenje problema LP. Za dvodimenzionalni slučaj razmatran u § 7.6, osnovna rješenja su svih 6 točaka, a dopuštena osnovna rješenja su točke L, V, Si 0.

Dakle, bilo koji vektor x sličan x° može se napisati kao

Gdje x in- vektor čiji elementi odgovaraju linearno nezavisnim stupcima matrice A; xF - vektor s nula elemenata.

Na sličan način definirajmo vektore

Varijable koje su elementi vektora x u, se zovu osnovne varijable te varijable koje su elementi vektora x F se zovu besplatno (nebazične) varijable.

Jer x° F=0, tada će vrijednost funkcije cilja za početni vektor x° biti jednaka

gdje je /° vrijednost / u točki x°.

Poziva se rješenje (8.1) oblika [x°/°]t za x > 0 očito (eksplicitno) rješenje. Dakle, ako nebazične varijable postavimo na nulu, dobivamo očito rješenje.

Radi praktičnosti, preuredimo red T linearno nezavisni stupci matrice A u lijeva strana i upiši matricu u obrazac

Ovdje odgovara matrica B T linearno neovisni stupci ima dimenziju tx t i rang T, i matrica F

je tx (p - t) matrica. Budući da se matrica B sastoji od linearno neovisnih stupaca, ona ima inverz B -1 i detB φ 0. Imajte na umu da za formiranje matrice B možete odabrati bilo koju T linearno nezavisni stupci matrice A.

Predstavimo problem (8.1) uzimajući u obzir uvedenu notaciju

Ovaj prikaz odgovara proširenoj matrici. Pretpostavimo da

odakle slijedi

Ako je vektor x V bude rješenje sustava Bx d = b, tada će to biti osnovno rješenje. Ako nejednakost vrijedi V= B -1 b > O, tada x in bit će prihvatljivo rješenje.

Tako, trenutno rješenje zadovoljava sljedeću jednadžbu:

Razmotrimo matricu (8.4). Osnovne varijable bit će prikazane u eksplicitno, ako matricu B zamijenimo matricom identiteta I. Množenjem prvog reda matrice (8.4) lijevo s B~ 1, dobivamo

gdje je B_1 b > O, tj. T gornji elementi u desnom stupcu su nenegativni i predstavljaju trenutnu vrijednost varijabli.

S lijeve strane Gornji red Rezultat je jedinična matrica: B -1 B = I. Ova prezentacija vrlo zgodno, jer pri množenju vektorom x in svaka varijabla će biti u zasebnoj liniji.

Dakle, osnovno rješenje, koje ćemo smatrati dopustivim i koje odgovara bazi B, je x m = [x u 0], gdje je x u == B_1 b. Osnovno rješenje proizlazi iz pretpostavke da x F = 0. Međutim, ako xF* 0, tada se x^ može izračunati kao x 5 = = B~"b - B^"Fx/r. Zamjenom ovog izraza u ciljna funkcija(funkcija troška), dobivamo

Budući da je potrebno utvrditi ovisnost troška o nebazičnim varijablama, od kojih se jedna onda ubraja u osnovne, donja crta pod matricom I trebala bi biti nula. Da bismo to učinili, u (8.7) prvi redak (matrice) množimo s od do i dodajte ga drugom

gdje je vrijednost funkcije cilja za početno stoljeće

torus x 0 iz (8.3).

Matrica (8.8) se zove simplex tablica. Dovodeći je do ove vrste je početno stanje simpleks algoritam. Tijekom izvođenja algoritma vrši se prijelaz s jedne tablice na drugu sve dok donji desni element tablice ne postane maksimum ili minimum.

Korištenjem simpleks tablice lako je vidjeti izvedivo rješenje. Varijable x F odgovaraju nultoj submatrici, varijable x in- jedinična matrica:

Pretpostavimo da je problem LP sveden na standardni oblik, da je izračunata simpleks tablica i da je odabrano početno osnovno rješenje koje odgovara vrhu poliedra rješenja.

Zatim - rješenje problema (8.1). Tako

kao b > Oh, ovo je osnovno prihvatljivo rješenje.

Predstavimo matricu (8.9) u prikladnijem obliku, zadržavajući osnovne oznake:

Razmotrimo odvojeno probleme maksimizacije i minimizacije.

Pronalaženje optimalnog plana. Ova metoda je univerzalna; omogućuje rješavanje problema linearnog programiranja bilo koje dimenzije u općoj formulaciji. Međutim, ova metoda zahtijeva svođenje izvornog problema na kanonski oblik.

Glavna ideja simpleks metode je prelazak s jednog vrha ODR-a na drugi tako da sa svakim prijelazom vrijednost CF-a opada. Ovako možete doći od bilo kojeg vrha do optimalnog i dobiti optimalan plan.

Na primjer: neka je poznat referentni plan X =(x1,x2,…,xm,0,0,…,0) i pridruženi sustav linearno neovisnih vektora: A1,A2,…,Am, tada za ovaj referentni plan možete izračunati vrijednost CF Z=(c1x1+c2x2+…+cmxm) i zapisati uvjete ograničenja u sljedeći obrazac x1A1+x2A2+…+xmAm=b

Budući da su vektori A1, A2,…, Am linearno neovisni, bilo koji vektor Aj može se proširiti u ove vektore: Aj=x1jA1+x2jA2+…+xmjAm (*) Uvedimo vrijednosti Zj Zj=x1jc1+x2jc2+…+ xmjcm, gdje je xij koeficijent koji odgovara Ai u vektoru proširenja Aj baznim vektorima

Teorem 1: Poboljšanje referentnog plana

Ako je za neki indeks j zadovoljen uvjet Zj-Cj>0, tada se vrijednost CF može smanjiti i:

· ako je CF ograničen odozdo, tada je moguće konstruirati referentni plan s manjom CF vrijednošću, istom prethodnom

· ako TF nije ograničen odozdo, tada je moguće konstruirati plan koji odgovara proizvoljno maloj vrijednosti TF

Teorem 2: kriterij optimalnosti za referentni plan

Ako za neki indeks j u referentnom planu nejednakost Zj-Cj0. Neka je taj minimum postignut za vektor Ak, tada je taj vektor taj koji se mora izvesti iz baze. Pravac koji odgovara ovom vektoru naziva se vodič i označava se s "à".

4. Nakon definiranja vodiča za stupce i retke, ispunite novu simplex tablicu. U takvoj tablici, Ai će se pojaviti umjesto linije vodilje. Punjenje novi stol počinje s vodećom linijom. Kao sastavni dio referentnog plana, tu je zapisana vrijednost Ө0 X'l=Ө0=Xk/Xkl, preostali elementi ovog retka određeni su formulom X'lj X'lj=Xkj/Xkl gdje je Xkl element nalazi se na sjecištu vodilica reda i stupca, odnosno na njemu se dijele svi dosadašnji elementi linije vodilice, a na mjestu nekadašnjeg Xkl elementa automatski se pojavljuje jedinica. Opće pravilo da biste ponovno izračunali vodeću liniju, možete je napisati ovako: Ak (novi element vodeće linije) = (stari element vodeće linije)/(element koji stoji na raskrižju vodećeg stupca i reda)

5. Ponovno se izračunavaju svi elementi preostalih redaka tablice, uključujući i dodatne Poanta. Ponovno izračunavanje se provodi prema formulama

· za komponente referentnog plana X’i=Xi-Ө0Xil=Xi-(Xk/Xkl)*Xil

· za komponente proširene preko baze X’ij=Xij-(Xkj/Xkl)*Xil

· Za dodatna linija Z’j-Cj=(Zj-Cj)-(Xkj/Xkl)*(Zl-Cl)

Sve ove formule izgrađene su prema jednom pravilu:

(nova e-pošta)=(stara e-pošta)-(nova e-pošta o smjeru retka)*(e-pošta o smjeru stupca u odgovarajućem retku)

Nakon popunjavanja nove simpleks tablice dolazi do prijelaza na drugu fazu algoritma.

Metode prirodnog i umjetna osnova. Osnovni pojmovi, algoritmi metoda.

Za većinu problema linearnog programiranja nastaju poteškoće u rješavanju povezanih s određivanjem početnog referentnog plana i početne simpleks tablice od koje počinju sve iteracije. To je zbog činjenice da u stvarnim problemima među vektorima Ai nema vektora koji sadrže samo jednu različitu od nule komponentu, tj. vektora oblika (0,0,0,…,0,1,0,…,0) ili njihov broj nije dovoljan da čini osnovu. Odnosno, nije moguće formirati prirodnu osnovu.

Metoda umjetne osnove temelji se na umjetni uvod V matematički model problemi takvih vektora.

Neka se da ZLP kanonski oblicima

F: C1X1=C2X2+…+CnXnàmin

a11x1+a21x2+…+an1xn=b1

a12x1+a22x2+…+an2xn=b2

…………………………

a1mx1+a2mx2+…+anmxn=bm

Zatim se pretvara u obrazac

F: C1X1+C2X2+…+CnXn+MXn=1+MXn+2+…+MXn+màmin

a11x1+a21x2+…+an1xn+xn+1=b1

a12x1+a22x2+…+an2xn+xn+2=b2

……………………………….

a1mx1+a2mx2+…+anmxn+xn+m=bm

Gdje je M beskonačno veliki brojevi. U rezultirajućem problemu početna baza je odmah vidljiva, a za nju treba uzeti vektore s umjetno uvedenim varijablama xn+1, xn+2,…, xn+m. Budući da će ti vektori imati oblik: (1,0,0,…,0),(0,1,0,…,0),(0,0,…,1). Transformirani problem se zatim rješava pomoću algoritma simpleks metode. Početni referentni plan transformiranog problema ima oblik (0,0,…,0,xn+1,xn+2,…,xn+m)=(0,0,…,0,b1,b2,…, bm). Originalna simplex tablica izgleda ovako:

Osnova	koeficijent CF	Plan	C1	C2	…	Cn	M	M	…	M
			A1	A2	…	An	An+1	An+2	…	An+m
An+1	M	b1	a11	a21	…	an1	1	0	…	0
An+2	M	b2	a12	a22	…	an2	0	1	…	0
…	…	…	…	…	…	…	…	…	…	…
An+m	M	bm	a1m	a2m	…	anm	0	0	…	1
			Z0

Elemente dodatnog voda određujemo pomoću formula Z0=Mb1+Mb2+…+Mbm=∑mi=1Mbi=M∑ni=1bi

Za određivanje razlika Zj=a11M+Ma12+…+Ma1m=M∑mj=1aij V i=1,n

Zj-Cj=M∑mj=1aij-Cj

Nakon primanja originalne simpleks tablice, ona se transformira, pokušavajući izvesti iz baznih vektora koji odgovaraju uvedenim dodatnim varijablama.

Pošto je M vrlo veliki broj, tada će među razlikama Zj-Cj biti mnogo pozitivnih brojeva. To jest, bit će mnogo kandidata za uključivanje u bazu među vektorima A1,A2,…,An

Ako neki vektor odgovara umjetno uvedenim varijablama xn+1,xn+2,…,xn+m, tada se odgovarajući vektor izvodi iz baze, a simpleks stupac tablice s tim vektorom se precrtava i ne vraća ponovno na to. Na kraju transformacije simpleks tablice moguće su dvije opcije:

· svi vektori koji odgovaraju umjetnim varijablama su izvedeni iz baze, u ovom slučaju svi stupci simpleks tablice koji odgovaraju dodatnim varijablama će nestati, a rješenje će biti izvorni problem

· rezultirajući optimalni plan će i dalje sadržavati neke dodatne varijable, to znači da je ODD izvornog problema prazan, tj. njegova ograničenja su kontradiktorna, stoga izvorni problem uopće nema rješenja.

Problemi dualnog linearnog programiranja. Postavka problema, njihova svojstva.

Simetrični dualni problemi:

Prvi standardni obrazac

f(x)=c1x1+c2x2+…+cnxnàmin

a11x1+a21x2+…+an1xn>=b1

a12x1+a22x2+…+an2xn>=b2

…………………………………………..

a1mx1+a2mx2+…+anmxn>=bm

Dvostruki problem

d(y)=b1y1+b2y2+…+bmymàmax

a11y1+a12y2+…+a1mym=0, V j=1,m

Neseptenarni par dualnih problema

Izvorni problem u kanonski oblik

f(x)=c1x1+c2x2+…+cnxnàmin

a11x1+a21x2+..+an1xn=b1

a12x1+a22x2+..+an2xn=b2

…………………………..

2. Uvođenje prirodnih osnovnih varijabli. Konstrukcija simpleks tablice. Definicija nultog plana.

Simpleks metoda. Algoritam simpleks metode.

Simpleks metoda- algoritam za rješavanje optimizacijskog problema linearnog programiranja nabrajanjem vrhova konveksnog poliedra u višedimenzionalnom prostoru. Metodu je razvio američki matematičar George Danzig 1947. godine.

Ideja simpleks metode je da se postavljeni opisni problem prevodi u matematički oblik. Matematička formulacija problema sadrži jednadžbu funkcije cilja koja ukazuje na željeni rezultat - određivanje minimuma ili maksimuma funkcije cilja; sustava linearna ograničenja, zadane jednakostima ili nejednakostima. Dobiveni matematički opis dovodi do matrični oblik. Tada se matrični opis problema svodi na kanonski oblik. Nakon sustava linearne jednadžbe reduciran u kanonski oblik, počinjemo rješavati problem linearnog programiranja. Algoritam za rješavanje ovog problema sastoji se od niza konstruiranja matrica. Svaki korak rješenja približava vas željenom rezultatu.

U računskoj shemi simpleks metode implementira se uređeni proces u kojem se, počevši od neke početne dopuštene kutne točke (obično ishodišta), uzastopni prijelazi od jedne dopuštene ekstremne točke do druge dok se ne nađe točka koja odgovara optimalnom rješenju. pronađeno.

Algoritam Simplex metode

1. Sustav ograničenja dovodimo u kanonski oblik (kada je sustav ograničen). Štoviše, u sustavu se može identificirati jedna jedina osnova.

2. Pronađite original referentni plan(nenegativna osnovna rješenja sustava jednadžbi KZLP). Svaki od referentnih planova određen je sustavom od m linearno neovisnih vektora sadržanih u zadanom sustavu od n vektora A 1 , A 2 ,…, A n. Gornja granica broja referentnih planova sadržanih u danom problemu određena je brojem kombinacija S nm);

3. Mi gradimo simplex tablica (simplex tablica matrica koja služi kao sredstvo za nabrajanje dopuštenih baznih rješenja (nedegeneriranog) problema linearnog programiranja pri njegovom rješavanju pomoću simpleks metode. Formira se iz matrice koeficijenata sustava linearnih programskih jednadžbi svedenih na kanonski oblik njegova sekvencijalna transformacija prema tzv. ekstremna vrijednost funkcije cilja).

4. B simplex tablica provjeravamo vektore na negativnost, tj. procjene Zj – Sj napisano u retku mora biti ≤ 0 (najmanje), Zj – Sj ≥ 0(do maksimuma). Ako procjene zadovoljavaju uvjete optimalnosti, tada je problem riješen.

5. Ako su za neke vektore povrijeđeni uvjeti optimalnosti, tada je potrebno uvesti u bazu vektor koji odgovara:

max [θ 0 j (Zj – Sj)] ; min [θ 0 j (Zj – Sj)] ; θ 0 j = min, Gdje x i> 0

Vektorski element θ jšto odgovara θ 0 j naziva se permisivnim; redak i stupac u kojem se nalazi nazivaju se vodič; vektor u redu vodiča napušta bazu.

6. Nađimo koeficijent ekspanzije za sve vektore u novoj bazi. Primijenimo metodu Giordana Gaussa

Provjerimo optimalan referentni plan. Ako procjena zadovoljava uvjete optimalnosti, tada je problem riješen; ako ne, tada se izvode koraci 5-7.

2. Uvođenje prirodnih osnovnih varijabli. Konstrukcija simpleks tablice. Definicija nultog plana.

Simpleks metoda je najučinkovitija u rješavanju složenih problema i predstavlja iterativni (korak po korak) proces koji počinje s nula(referentno) rješenje (vrh n-dimenzionalni poliedar). Sljedeći u potrazi optimalna opcija Plan pretpostavlja kretanje duž kutnih točaka (vrhova poliedra) dok vrijednost ciljne funkcije ne dosegne najveću (minimalnu) vrijednost. Razmotrimo algoritam simpleks metode na primjeru problema planiranja prometa za ograničeni resursi sirovine.

Tvrtka prodaje n grupe proizvoda, imajući m ograničena materijalna i novčana sredstva b i ≥0 (1 ≤ ja≤ m) . Svima su poznati troškovi resursa ja- vrsta proizvodnje i prodaje jedinice robe svake skupine, prikazana u obliku matrice ( a ij) i dobit koju poduzeće primi od prodaje jedinice robe j-skupina uključena u funkciju cilja Z(x). Metoda linearnog programiranja ne razlikuje se od sustava (1) - (2):

Z(X) = s 1 H 1 + s 2 H 2 + s 3 H 3 + … +s ​​n H n →max(min) (1)

a 11 X 1 + a 12 X 2 +…a 1n X n ≤ b 1,

a 21 X 1 + a 22 X 2 +…a 2n X n ≤ b 2 (2)

a m1 X 1 + a m2 X 2 +…a mn X n ≤ b m,

X 1 ≥0 X 2 ≥0 X 3 ≥0 …X n ≥0

Faze rješavanja problema pomoću simpleks metode uključuju:

1) Izrada nultog referentnog plana. Uvodimo nove nenegativne (bazične) varijable, zahvaljujući kojima sustav nejednadžbi (2) postaje sustav jednadžbi:

a 11 X 1 + a 12 X 2 +…a 1n X n + X n+1 = b 1

a 21 X 1 + a 22 X 2 +…a 2n X n + X n+2 = b 2 (3)

……………………………………..

a m1 X 1 + a m2 X 2 +…a mn X n + X n+m = b m,

Ako ulazne varijable uzmemo kao vektore stupaca, tada one predstavljaju singl (Osnovni, temeljni) vektori. Imajte na umu da osnovne varijable imaju jednostavnu fizičko značenje- Ovo ostatak specifični resurs u skladištu za zadani proizvodni plan, stoga se ova osnova naziva prirodni. Sustav (3) rješavamo s obzirom na osnovne varijable:

X n+1 = b 1, -a 11 X 1 - a 12 X 2 -…a 1n X n

X n+2 = b 2 - a 21 X 1 - a 22 X 2 -…a 2n X n (4)

………………………………………..

X n+m = b m, - a m1 X 1 + a m2 X 2 +…a mn X n

Prepisujemo funkciju cilja u obliku

Z(X) = 0-(-s 1 H 1 -s 2 H 2 -s 3 H 3 -…-s n H n) (5)

Uz pretpostavku da su potrebne glavne varijable X 1 = X 2 = X 3 = ... = X n = 0, dobivamo nulti referentni plan X = (0, 0, ...0, b 1, b 2, b 3 ... b m), pri čemu je Z(X) = 0 (svi resursi na zalihama, ništa proizvedeno). Plan unosimo u simplex tablicu.

Plan	Osnova	C i /C j	Značenje X i	X 1	X 2	Xn	Xn+1	Xn+2	X n+ 3	Q min
	Xn+1		b 1	a 11	a 12	a 13				b 1/a 12
Xn+2		b 2	a 21	a 22	a 23				b 2 / a 22
Xn+3		b 3	a 31	a 32	a 33				b 3 / a 32
Z(X) = 0	-C 1	- C 2	- C 3				Indeks. crta

2) Od negativnih koeficijenata indeksne linije odaberite najveći apsolutna vrijednost, koji određuje vodeći stupac i pokazuje koja će varijabla u sljedećoj iteraciji (koraku) prijeći iz glavne (besplatne) u osnovnu (zapravo se odabire grupa proizvoda čija prodaja donosi maksimalan prihod). Potom zalihe sirovina b i podijelimo s pripadajućim troškovnim koeficijentima, rezultate unesemo u tablicu i odredimo minimalnu vrijednost Q min (odabire se resurs čija zaliha najjače ograničava učinak odabrane grupe proizvoda). Ova vrijednost odabire vodeću liniju i varijablu Xi koja će u sljedećem koraku (iteraciji) napustiti bazu i postati slobodna.

3) Prijelaz na novi plan provodi se kao rezultat ponovnog izračuna simpleksne tablice pomoću metode Jordan-Gauss. Prvo, zamijenimo X j u bazi s X i vodećeg stupca. Podijelimo sve elemente vodeće linije razlučujućim elementom (RE), zbog čega će mjesto RE u vodećoj liniji biti 1. Kako je X i postao osnovni, njegovi preostali koeficijenti trebaju biti jednaki 0. .Novi elementi ovog plana nalaze se prema pravilu pravokutnika

NE=SE – (A*B)/RE (6)

Rezultirajući plan se ocjenjuje pomoću koeficijenata indeksne linije: ako su svi pozitivni, tada je plan optimalan, ako nije, tada se plan može poboljšati izvođenjem sljedeće iteracije (korak).

Primjer. Za kupnju opreme za proizvodno mjesto izdvojeno je 20 tisuća rubalja. Oprema se može postaviti na površini koja ne prelazi 72 m2. Možete naručiti opremu dvije vrste: tip A, koji zahtijeva proizvodnu površinu od 6 m2 i nudi 6 tisuća jedinica. proizvodi po smjeni (cijena 5000 rubalja) i tip B, koji zahtijevaju površinu od 12 m² i proizvode 3 tisuće jedinica (cijena 2000 rubalja). Koji je optimalan plan nabave opreme osigurati maksimalne performanse zemljište?

Označimo količinu kupljene opreme tipa A i B s X 1 odnosno X 2.

Produktivnost mjesta (funkcija cilja): Z(X) =6H 1 +3H 2.

Glavna ograničenja su povezana

s gotovinom: 5H 1 +2H 2 ≤ 20,

s površinom proizvodnog mjesta: 6H 1 +12H 2 ≤ 72.

Uvodimo nove osnovne varijable X 3 (ostatak Novac nakon nabave opreme) i X 4 (preostala površina nakon postavljanja opreme) te prepišite ograničenja u obliku sustava jednadžbi:

5X 1 +2X 2 +X 3 =20 (X 3 =20 – 5X 1 - 2X 2)

6X 1 +12X 2 +X 4 = 72 (X 4 =72 – 6X 1 – 12X 2)

U ovom slučaju funkcija cilja: Z(X) = 6H 1 +3H 2 +0H 3 +0H 4 .

Izrađujemo referentni (0.) plan: X = (0, 0, 20, 72), t.j. još ništa nije kupljeno (novci nisu potrošeni, prostor je prazan). Izrada simpleks tablice

Plan	Osnova	C i /C j	Značenje X i	X 1	X 2	X 3	X 4	Q min
	X 3							20/5=4
X 4							72/6=12
Z(X) = 0	- 6	- 3			Indeksna linija
	→ X 1				0,4	0,2		4/0,4=10
X 4				9,6	-1,2		48/9,6=5
Z(X) = 6*4=24		-0,6	1,2		Indeksna linija
	X 1					0,25	-1/24	-
→ X 2					-1/8	5/48	-
Z(X) =6*2+3*5=27			9/8	1/16	Indeksna linija

Očito, vodeći stupac odgovara X 1, budući da ima najveći indeks 6. Nalazimo minimalnu vrijednost Q min = 4 (najstrože ograničenje resursa) definiranjem vodećeg retka koji pokazuje da je X 3 izveden iz osnovnih varijabli , a X se upisuje umjesto 1 . Preračunamo elemente vodeće crte, podijelimo ih s 5, te pomoću formule (6) odredimo elemente druge i indeksne crte. Funkcija cilja za 1. plan jednaka je Z(X) = 6*4+3*0 = 24.

Međutim, jedan od koeficijenata retka indeksa za stupac X 2 ostaje negativan -0,6, dakle ovaj plan nije optimalan i potrebna je još jedna iteracija (korak) da se poboljša. Odaberite 2. stupac kao vodeći i minimalna vrijednost Q min = 5 definiramo vodeću liniju s osnovnom varijablom X 4. Provođenjem istih transformacija dobivamo 2. plan koji će biti optimalan jer su svi koeficijenti indeksa pozitivni.

Analizirajmo dobivene rezultate. Na optimalno rješenje objektivna funkcija ima maksimalna vrijednost 27 tisuća rubalja, dok su oba resursa izvađena iz baze, dakle potpuno potrošena.

Uvjerimo se u ovo: 5*2+2*5 = 20 tisuća rubalja, 6*2+12*5=72 m². Traženo rješenje je X = (2; 5;0;0). To se ne događa uvijek.

Predavanje br.10

Tema: Simpleks metoda za probleme s umjetnom osnovom

Simpleksna metoda rješenja temelji se na uvođenju dodatnih (osnovnih) varijabli koje omogućuju formiranje jedinične matrice. Ako su ograničenja problema predstavljena u obliku nejednakosti:

a i1 X 1 + a i2 X 2 +…a u X n ≥ b i (1)

ili jednadžbe:

a i1 X 1 + a i2 X 2 +…a u X n = b i (1*),

tada je nemoguće dobiti referentni plan u željenom obliku. U ovom slučaju, da bismo zadovoljili jednakosti (1*), uvodimo umjetna osnova Y i , a umjetne varijable nisu izravno povezane sa sadržajem zadatka, ali omogućuju konstruiranje referentnog (polaznog) plana:

a i1 X 1 + a i2 X 2 +…a u X n +Y i = b i (2)

Funkcija cilja pri maksimalnom rješavanju problema bit će zapisana u obliku:

Z(X) =∑C j X j +(-M)∑Y i (3),

pri rješavanju sličnog problema minimalno:

Z(X)=∑C j X j +(M)∑Y i (3*),

gdje je M vrlo velik pozitivan broj, svojevrsna kazna za korištenje umjetnih varijabli.

U slučaju nejednakosti (1) u početku uvodimo dodatne varijable X n + i s predznakom minus. Njihova matrica neće biti unitarna, stoga u svaku nejednadžbu sustava (1) uvodimo umjetne varijable U i:

a i1 X 1 +a i2 X 2 +…a u X n –X n+i +Y i =b i (4)

Funkcija cilja u ovom slučaju je Z(X)=∑C j X j +0∑X n + i +(-M)∑Y i (za pronalaženje maksimuma). Korištenje umjetne osnove daje simpleks metodi veću fleksibilnost i omogućuje njezinu primjenu za širok raspon problema.

Primjer . Odrediti maksimalnu i minimalnu vrijednost dobiti za proizvodnju dvije vrste proizvoda A i B, ako su u tablici dani troškovi proizvodnje i profitabilnost od prodaje jedinice proizvoda. Glavni uvjet je puna zaposlenost radnika u poduzeću.

Matematički, ograničenja proizvodnje bit će zapisana u obliku mješovitog sustava:

1H 1 + 1H 2 ≤ 6,

2X 1 + 1X 2 =8.

Uvedimo osnovnu varijablu X 3 za prvu nejednadžbu, a umjetnu varijablu Y 1 za drugu jednadžbu:

1X 1 + 1X 2 + X 3 = 6,

2X 1 + 1X 2 +Y 1 =8.

Izrazimo X 3 i Y 1 iz rezultirajućeg sustava jednadžbi i, da odredimo maksimum, zamislimo funkciju cilja:

Z(X)= 3X 1 + 2X 2 +0X 3 –MY 1 = 3X 1 + 2X 2 –M(8 -2X 1 –X 2)=

3X 1 + 2X 2 –8M +2MX 1 + MX 2 = (2M + 3)X 1 + (M + 2)X 2 -8M

Za referentni plan - X=(0,0,6,8). Napravimo simpleks tablicu:

Plan	Osnova	C i /C j	Značenje X i	X 1	X 2	X 3	Y 1	Q min
	X 3							6/1=6
Y 1	-M						8/2=4
Z(X) = -8M	-2M-3	-M-2			Indeksna linija
	X 3				0,5		-0,5	2/0,5=4
→ X 1				0,5		0,5	4/0,5=8
Z(X) = 3*4=12		- 0,5		M+1,5	Indeksna linija
	→ X 2						-1	-
X 1					-1		-
Z(X) =3*2+2*4=14				M+1	Indeksna linija

Poboljšanje referentnog plana u pravilu počinje uklanjanjem umjetne varijable Y 1 iz baze. U drugoj iteraciji dobiven je optimalni plan X = (2,4,0,0), s maksimalnim prihodom od 14. tisuću. trljati. , a koeficijenti indeksnog reda su nenegativni. Lako je provjeriti da su u ovom zadatku, uz optimalan plan, resursi u potpunosti iskorišteni (2*1+4*1=6; 2*2+1*4=8).

Kod pronalaženja minimalne profitabilnosti, funkciju cilja drugačije formuliramo (+MY 1 se unosi kao pojam:

Z(X)= 3X 1 + 2X 2 +0X 3 +MY 1 = 3X 1 + 2X 2 +M(8 -2X 1 –X 2)=

3X 1 + 2X 2 +8M - 2MX 1 - MX 2 = (3 - 2M)X 1 + (2 - M)X 2 +8M

Osnovni plan isti, ali koeficijenti reda indeksa u simpleks tablici su različiti. Vodeći stupac, kao i prije, odabire najveći apsolutna vrijednost pozitivan koeficijent za X 1, vodeći red je određen minimalnom vrijednošću Q min =4 U prvoj iteraciji, umjetna varijabla Y 1 je izvedena iz baze.

Plan	Osnova	C i /C j	Značenje X i	X 1	X 2	X 3	Y 1	Q min
	X 3							6/1=6
Y 1	M						8/2=4
Z(X) = 8M	2M-3	M-2			Indeksna linija
	X 3				0,5		-0,5	2/0,5=4
→ X 1				0,5		0,5	4/0,5=8
Z(X) = 3*4=12		- 0,5		-M+1,5	Indeksna linija

Rezultirajuće negativne vrijednosti koeficijenata u indeksnoj liniji X i ukazuju na optimalnost 1. plana, dok je minimalni prihod 12 tisuća rubalja.

Osigurava se samo outputom proizvoda A (proizvod B se ne proizvodi), sirovine nisu u potpunosti iskorištene (ostatak X 3 = 2t), dok je glavni uvjet ispunjen - radnici su potpuno zaposleni u proizvodnji.

Predavanje br.11

Tema: Problem zatvorenog prometa

1. Matematička formulacija zatvorenog transportni problem. Određivanje potrebnog broja nepoznanica.

2. Faze utvrđivanja plana rješavanja prometnog problema.