Tablični prikaz PPP-a. Simplex - tablice.

JEDNOSTAVNA METODA RJEŠAVANJA ZLP

3.1. Opće karakteristike te glavne faze simpleks metode

Utemeljitelji simpleks metode su sovjetski matematičar L.V. Kantorovich i američki matematičar J. Dantzig.

Simpleks metodom možete riješiti bilo koji problem ili otkriti njegovu nerješivost. Mnoge posebne klase problema mogu se riješiti drugim metodama koje su učinkovitije za te klase. Međutim, prednost simplex metode je njezina svestranost. Gotovo sva računala su razvijena standardni programi riješiti ZLP simpleks- metoda.

Hajdemo opisati opća ideja simpleks metoda.

Smatramo da je ZLP napisan u kanonskom obliku te da je ciljnu funkciju potrebno minimizirati. Kao što već znamo, optimalni plan treba tražiti među osnovnim planovima ZLP-a. Simpleks metoda ne prolazi kroz sve referentne planove (što bi često bilo nemoguće zbog njihovog velikog broja), već se, počevši od nekog početnog referentnog plana, sekvencijalno prelazi na druge referentne planove sa smanjenjem objektivna funkcija. Simpleks metoda prestaje raditi kada se pronađe optimalni referentni plan ili se utvrdi nerješivost problema.

Prilikom odlučivanja ZLP pomoću simpleks metode Mogu se razlikovati sljedeće faze:

1) dovođenje PAP-a na kanonski oblik;

2) dovođenje sustava linearnih jednadžbi u Jordanov oblik s nenegativnim desnim stranama uz istovremenu provjeru nerješivosti ZLP-a zbog nekonzistentnosti sustava linearna ograničenja;

3) elaborat referentnog plana za optimalnost;

4) proučavanje ZLP na neodlučivost zbog neograničenosti odozdo na ODD funkcije cilja;

5) prelazak na novi, „bolji“ referentni plan.

Za smanjivanje i organiziranje zapisa pri rješavanju ZLP-a simpleks metodom koriste se tzv. simpleks tablice. Za korištenje simplex tablice, ZLP se mora pretvoriti u tablični oblik. To se radi ovako.

Neka ZLP bude napisan u kanonskom obliku (2,3-2,5). Da bi se ZLP sveo na tablični oblik, sustav (2.4) treba prvo reducirati na Jordanov oblik s nenegativnim desnim stranama. Pretpostavimo da ovaj Jordanov oblik ima oblik (2.6). Izrazimo iz (2.6) osnovne varijable kroz slobodne:

Zamjenom u funkciji cilja (2.3) umjesto osnovnih varijabli njihove izraze preko slobodnih varijabli prema formulama (3.1), isključujemo osnovne varijable iz funkcije cilja. Ciljna funkcija će imati oblik:

U tablični oblik funkcija cilja se piše na sljedeći način:

Gdje .

Bilješka sljedeće karakteristike tablični oblik PPP-a:

a) sustav linearnih jednadžbi reducira se na Jordanov oblik s nenegativnim desnim stranama;

b) bazne varijable isključene su iz funkcije cilja i zapisana je u obliku (3.3).

Prijeđimo sada na opis simpleks tablice. Neka ZLP bude napisan tabelarno:

(3.4)

Tada završena simpleks tablica izgleda ovako.

Simpleksna metoda rješavanja problema linearno programiranje

Simpleks metoda je analitička metoda ZLP rješenja koja implementiraju algoritam grafička metoda analitički, bez crtanja crteža.

Dakle poanta je simpleks metoda sastoji se od usmjerenog traženja izvedivih rješenja, pri čemu je vrijednost funkcije cilja u svakom koraku bolja nego u prethodnom. Proces se ponavlja dok se ne dobije rješenje koje je optimalno s obzirom na vrijednost funkcije cilja.

Simpleks metoda se može koristiti za rješavanje PLP-ova s ​​bilo kojim brojem nepoznanica.

Tehnička implementacija simpleks metode povezana je s rješavanjem sustava linearnih jednadžbi, za što se koristi Gaussova metoda, razvijeni su tablični oblici i pravila za pretvaranje simpleks tablica.

Simplex metoda s prirodnom osnovom primjenjuje se ako je PIL naveden u kanonski oblik zapisa, a matrica u KZLP sadrži jediničnu podmatricu veličine m´m. Za sigurnost pretpostavimo da je prvi m Vektorske matrice sustava jednadžbi čine matricu identiteta. Zatim se odabire početni plan na sljedeći način:

Optimalnost referentnog plana provjerava se pomoću predznaka optimalnosti, prijelaz na drugi plan provodi se pomoću Jordan-Gaussove transformacije pomoću matematičkog predznaka optimalnosti. Dobiveni referentni plan ponovno se provjerava na optimalnost, itd.

Matematički kriterij optimalnosti sastoji se od sljedeća dva teoreme:

1. Ako za sve vektore A 1 , A 2 , … , A n uvjet je zadovoljen gdje , tada je rezultirajući referentni plan optimalan. Ukupno utvrditi Z j sudjelovati m termi, odnosno u njemu ne sudjeluju svi koeficijenti funkcije cilja c j, ali samo s brojevima koji odgovaraju brojevima vektora trenutne baze A i, čiji je broj jednak m .

2. Ako je za neki vektor koji nije uključen u bazu uvjet zadovoljen , tada biste trebali potražiti novi referentni plan za koji je CF vrijednost veća nego za trenutni. U ovom slučaju moguća su dva slučaja:

a) ako su sve komponente vektora A k, koji se unose u bazu su nepozitivni, tada LLP nema rješenja (nema konačnog optimuma);

b) ako vektor ima barem jednu pozitivnu komponentu A k, unijeti u osnovu, tada se može dobiti novi referentni plan.

Na temelju kriterija optimalnosti u bazu se uvodi vektor A k, što je dalo minimalnu negativnu vrijednost simpleks razlike:

Da bi uvjet nenegativnosti vrijednosti referentnog plana bio zadovoljen, vektor se izvodi iz baze A r, što daje minimalni omjer pozitivne ocjene

Linija A r, u kojem se nalazio stari bazni vektor, naziva se vodilica, stupac A k i element a rk- vodiči.

Elementi vodeće linije u novoj jednostavnoj tablici izračunavaju se pomoću formula:

i bilo koje druge elemente ja redak - prema formulama:

Vrijednosti novog referentnog plana izračunavaju se pomoću sličnih formula:

,

Proces se nastavlja dok se ne dobije optimalan plan ili dok TF ne bude neograničen. Ako među razlikama Δ j , j=1, 2, … , n optimalnog plana, samo razlike koje odgovaraju baznim vektorima su nula, to ukazuje na jedinstvenost optimalnog plana. Ako nulta procjena odgovara vektoru koji nije uključen u bazu, onda to u općem slučaju znači da optimalni plan nije jedinstven.

Primjer. Riješite ZLP pomoću modela:

pronaći ,

pod ograničenjima

Ovaj ZLP je sveden na kanonski oblik uvođenjem dodatnih varijabli x 3 I x 4:

KZLP ima potreban broj (dva) nula stupaca na x 3 I x 4, odnosno ima očit inicijal referentni plan (0,0,300,150).

Rješenje se provodi simpleks metodom s prirodnom osnovom s izračunima formatiranim u simpleks tablicama:

Jednostavni broj tablice	Osnova	sa j	sa j					Q
B	A 1	A 2	A 3	A 4
	←A 3
A 4
Δ	-		-2	-3			-
ja	→A 2			1/3		1/3
←A 4			2/3		-1/3
Δ	-		-1				-
II	A 2					1/2	-1/2	-
→A 1					-1/2	3/2	-
Δ	-				1/2	3/2	-

Zaustavimo se detaljnije o ispunjavanju simpleksnih tablica i, u skladu s tim, dobivanju KZLP rješenja.

U gornja linija koeficijenti uključeni u opću tablicu c j, j=1, 2, 3, 4 s varijablama u CF. Prva dva retka nulte simpleks tablice sadrže vektore stupaca B, A 1, A 2, A 3, A 4, što odgovara vektorskom obliku KZLP zapisa. Budući da je polazna baza par vektora A 3, A 4, oni su uključeni u stupac pod nazivom "Osnova" nulte simpleks tablice. Istovremeno, A 3 je uključen u prvi red, koji je određen jedinicom, koja je prvi element ovog vektora, i vektorom A 4- u drugu liniju, za ovaj vektor jedinica je u drugoj liniji. U stupcu pod nazivom " c i” uvode se koeficijenti funkcije cilja koji odgovaraju baznim vektorima A 3, A 4, odnosno c 3, c 4. Oba su jednaka nuli. Zatim se izračunavaju vrijednosti razlika Δ za vektore B, A 1, A 2, A 3, A 4 a upisuju se u treći red nulte tablice. Za vektor A 1:

za vektor:

Isto tako,.

Za vektor B izračun razlike je donekle pojednostavljen jer ne postoji odgovarajući koeficijent c j, j=1, 2, 3, 4 u CF:

Nije za sve vektore A 1, A 2, A 3, A 4 rezultirajuće razlike nisu negativne, tako da referentni plan koji smo odabrali nije optimalan. Moramo potražiti novi referentni plan, a za to moramo zamijeniti jedan od vektora uključenih u bazu A 3, A 4.

Da bismo odredili vektor koji moramo unijeti, tražimo vektor za koji je vrijednost razlike minimalna. Ovo je vektor A 2, odgovara tome minimalna vrijednost razlika: -3. Odnosno indeks k iz formule (8.4) jednaka je 2. Da bismo odredili vektor koji ćemo morati izvesti iz baze, izračunavamo vrijednosti Q za svaki red prema formuli (8.5) i unesite ih u zadnji stupac. U u ovom slučaju u svakom retku trebamo vrijednost vektorskog elementa B podijeliti s veličinom vektorskog elementa A 2. U prvom redu dobivamo 300/3=100, u drugom: 150/1=150. Omjer u prvom redu bio je manji; njemu je odgovarao bazni vektor A 3, dakle, indeks r u formuli (8.5) je jednak 1, a rk=3 (u tablici istaknuto okvirom), a vektor ćemo izvesti iz baze A 3(označeno strelicom u tablici).

Budući da među elementima vektora A 2, koji se moraju unijeti u osnovu, ima pozitivnih, zatim se može dobiti novi referentni plan i nastaviti s rješavanjem.

Nakon toga se popunjava druga simpleks tablica. Za ponovno izračunavanje vektorskih elemenata B, A 1, A 2, A 3, A 4 koriste se formule (8.6)-(8.8). Neznatno se razlikuju za definiranje elemenata linije vodilice (u našem slučaju prve) i za definiranje elemenata ostalih linija. Zapišimo izračune nekoliko elemenata:

Ostali elementi prve simpleks tablice izračunavaju se na isti način kao što smo to učinili za nultu tablicu. Budući da nisu sve razlike u prvoj simpleks tablici nenegativne, potrebno je nastaviti s izračunima.

Kao što vidimo, kao rezultat izračuna u drugoj simpleks tablici s baznim vektorima A 2, A 1 sve razlike pokazale su se nenegativnima, što znači postizanje optimalnog plana (75; 75; 0; 0). Simpleks razlika za vektor U jednak željenom maksimalna vrijednost CF - 375.

Teorem (o konačnosti simpleks algoritma).Ako postoji optimalno Odluka o JPP-u, tada postoji osnovno optimalno rješenje. Potonji se uvijek može dobiti pomoću simpleks metode, a možete krenuti od bilo koje početne baze.

Jedan od najčešćih i najpopularnijih problema optimizacije u logistici je transportni problem . U klasični izgled uključuje pronalaženje optimalnog ( one. povezan s minimalni troškovi ) plan prijevoza tereta.

Na primjer, imamo lanac maloprodajnih trgovina koji zahtijevaju određenu količinu robe. Postoji i niz skladišta dobavljača u kojima se skladišti potrebna roba. Štoviše, svako skladište ima različitu količinu zaliha te robe. Osim toga, znamo tarife - troškove prijevoza 1 proizvoda od svakog skladišta do svake trgovine.

Potrebno je izraditi plan prijevoza kako bi trgovine dobile potrebnu količinu robe uz najniže troškove prijevoza. Upravo u takvim slučajevima (i u mnogim drugim) treba riješiti problem transporta.

Teorijska građa o prometnom problemu

(Monge-Kantorovich problem) - matematički problem linearno programiranje posebna vrsta o potrazi optimalna raspodjela homogene objekte od baterije do prijemnika uz minimiziranje troškova putovanja.

Radi lakšeg razumijevanja, smatra se problemom optimalnog plana prijevoza robe s polazišta ( primjerice skladišta) do mjesta potrošnje ( na primjer, trgovine), uz minimalne ukupne troškove transporta.

Ima sljedeći oblik:

Gdje: Z- troškovi prijevoza robe;
X- obujam tereta;
C- trošak (tarifa) prijevoza jedinice tereta;
A- zaliha dobavljača;
B- zahtjev potrošača;
m- broj dobavljača;
n- broj potrošača.

Generalni plan rješenja prometnog problema metodom potencijala

Problem transporta se može riješiti razne metode, počevši od simpleks metode i jednostavnog nabrajanja, pa do . Jedna od najčešće korištenih i prikladnih metoda za većinu slučajeva je iterativno poboljšavanje plana prijevoza.

Njegova suština je sljedeća: nalazimo određeni referentni plan i provjeravamo ga optimalnost (Z → min). Ako je plan optimalan, rješenje je pronađeno. Ako nije, poboljšava plan onoliko puta koliko je potrebno dok se ne pronađe optimalni plan.

Ispod je algoritam za rješavanje transportnog problema u najopćenitijem obliku:

1. Izrada transportnog stola.
2. Provjera zadatka za zatvaranje.
3. Izrada osnovnog plana.
4. Provjera plana podrške za degeneraciju.
5. Proračun potencijala za prometni plan.
6. Provjera optimalnosti referentnog plana.
7. Preraspodjela zaliha.
8. Ako je pronađeno optimalno rješenje, idite na korak 9, ako nije, idite na korak 5.
9. Obračun ukupnih troškova transporta robe.
10. Konstrukcija transportnog grafa.

Detaljne upute za rješavanje transportnog problema

1. Izrada transportnog stola

Izrađujemo tablicu u kojoj označavamo zalihe materijala raspoložive u skladištima dobavljača ( Ai), te potrebe tvornica ( Bj) u ovim materijalima.

U donjem desnom kutu ćelija tablice unosimo vrijednost tarifa za prijevoz tereta ( Cij).

2. Provjera problema za zatvaranje

Simbolom označimo ukupnu zalihu tereta od svih dobavljača A, a simbolizira se ukupna potražnja tereta za sve potrošače B.

Transportni problem se zove Zatvoreno, Ako A=B. Ako A ≠ B, tada se transportni problem zove otvoriti. U slučaju zatvoreni problem Sve zalihe tereta bit će uklonjene od dobavljača, a svi zahtjevi potrošača bit će zadovoljeni. U slučaju otvoreni zadatak Da biste to riješili, morat ćete uvesti fiktivne dobavljače ili potrošače.

Provjerimo zadatak za zatvaranje:

A = 10 + 20 + 30 = 60

B = 15 + 20 + 25 = 60

A = B, stoga je ovaj transportni problem zatvoren.

3. Izrada referentnog plana

Sastavlja preliminarno ( podržavajući) plan prijevoza. Ne mora biti optimalno. Ovo je samo svojevrsni „nacrt“, „skica“, čijim ćemo usavršavanjem postupno doći do optimalnog plana.

Postoje različite metode za pronalaženje referentnog plana. Najčešći su sljedeći:

a) Metoda sjeverozapadnog kuta. Pokazati

Bit metode je jednostavna - ćelije transportne tablice uzastopno se popunjavaju najvećim mogućim količinama prometa u smjeru vrh prema dolje I s lijeva na desno. Odnosno, prva se popunjava gornja lijeva ćelija ( "sjeverozapadne" ćelije), zatim sljedeći s desne strane itd. Zatim idite na nova linija i ponovno ga ispunite s lijeva na desno. I tako dok se stol u potpunosti ne popuni.

Detaljan opis metode i primjer možete pronaći.

b) Metoda minimalnog elementa. Pokazati

Metoda je da za popunjavanje ćelija transportne tablice odaberete ćeliju sa minimalan tarifna vrijednost. Zatim se odabire sljedeća ćelija s najnižom tarifom i tako redom do popunjavanja tablice ( sve zalihe i potrebe bit će vraćene na nulu).

c) Vogelova aproksimacija. Pokazati

Osnova metode je pronalaženje razlike(modulo) između par minimalne tarife u svakom retku i stupcu. Zatim u retku ili stupcu sa najveći razlika ispunjava ćeliju sa najmanji tarifa. Zatim se sve te radnje ponovno ponavljaju, samo u ovom slučaju popunjene ćelije se više ne uzimaju u obzir.
Možete pronaći detaljan opis Vogelove aproksimacije i primjer

d) Metoda dvostrukih preferencija. Pokazati

Suština metode je da se ćelije s najnižom tarifom označavaju u redovima, a zatim u stupcima. Zatim se ćelije popunjavaju sljedećim redom: prvo ćelije sa dvije marke, zatim s jednom, na kraju bez oznaka.
Detaljan opis metode i primjer možete pronaći

4. Provjera plana podrške za degeneraciju

Pozivaju se ćelije tablice u kojima se bilježe prijevozi različiti od nule osnovni, a ostalo (prazno) - besplatno.

Plan se zove degenerirati, ako je broj osnovnih ćelija u njemu manji od m + n -1. Ako se tijekom rješavanja problema dobije degenerirani plan, tada se on mora nadopuniti umetanjem nultog transporta u nedostajući broj stanica i time pretvaranjem tih stanica u osnovne ( ukupna bilanca i ukupni trošak prijevoza plana neće se promijeniti). Međutim, nemoguće je nadopuniti plan nasumičnim odabirom ćelija. Plan mora biti acikličan!

Plan se naziva aciklički ako njegove osnovne ćelije ne sadrže cikluse. Ciklus u transportnoj tablici postoji nekoliko ćelija povezanih zatvorenom polilinijom tako da se dva susjedna vrha polilinije nalaze ili u istom retku ili u istom stupcu. Ispod je primjer petlje:

Izlomljena linija može imati samosjecišta, ali ne u ćelijama ciklusa.

Broj osnovnih ćelija = 5

m + n – 1 = 3 + 3 – 1 = 5

Posljedično, izvorni plan prijevoza nije degeneriran.

5. Proračun potencijala za prometni plan

Za analizu dobivenih planova i njihovo naknadno poboljšanje, prikladno je unijeti dodatne karakteristike točke polazišta i odredišta, koje se nazivaju potencijalima.

Ova metoda poboljšanja planova prijevoza naziva se potencijalna metoda . Postoje i druge metode za iterativno poboljšanje transportnog plana, ali ih ovdje nećemo razmatrati.

Dakle, usporedimo svakog dobavljača Ai i svakog potrošača Bj s vrijednostima Ui I Vj prema tome, tako da je za sve osnovne ćelije plana zadovoljen sljedeći odnos:

Ui + Vj = Cij

Dodati transportnoj tablici dodatna linija i stupac za Ui i Vj.

Pretpostavimo da je U1 = 0.

Tada možemo pronaći V3 = C13 – U1 = 1 – 0 = 1.

Poznavajući V3, sada možemo pronaći U3:

Analogno izračunavamo sve preostale potencijale:

6. Provjera optimalnosti plana metodom potencijala

Za svaku slobodnu ćeliju plana izračunavamo razlike

ΔCij = Cij – (Ui + Vj)

i zapišite dobivene vrijednosti u donji lijevi kut odgovarajućih ćelija.

Plan je optimalan, ako su sve razlike ΔCij ≥ 0.

U ovom slučaju plan je suboptimalan(ΔC22< 0), и его следует улучшить путем перераспределения поставок.

7. Preraspodjela zaliha

Pronađimo ćeliju s najvećim apsolutna vrijednost negativnu razliku ΔCij i konstruirati ciklus u kojem su, osim ove ćelije, sve ostale osnovne. Takav ciklus uvijek postoji i jedinstven je.

Označimo ćeliju s negativnom razlikom ΔCij znakom “+”, sljedeću znakom “-” i tako dalje, jednu po jednu.

Zatim pronađemo minimalnu vrijednost opterećenja u ćelijama ciklusa sa znakom "-" (ovdje je 5) i unesemo je u slobodnu ćeliju sa znakom "+". Zatim uzastopno prolazimo kroz sve ćelije ciklusa, naizmjence oduzimajući i dodajući im minimalnu vrijednost (u skladu sa znakovima kojima su te ćelije označene: gdje se minus oduzima, gdje se dodaje plus).

Dobivamo novi referentni plan prijevoz:

Budući da ima više osnovnih ćelija od m + n – 1, onda osnovna ćelija sa nulta vrijednost učini ga besplatnim:

Ponovno izračunavamo potencijalne vrijednosti i razliku ΔCij:

Ovaj put su sve razlike ΔCij stanica pozitivne, dakle, pronađeno optimalno rješenje.

8. Ako je pronađeno optimalno rješenje, idite na korak 9, ako nije, idite na korak 5.

Našli smo optimalno rješenje, stoga prijeđimo na točku 9.

9. Obračun ukupnih troškova transporta robe

Izračunajmo ukupni troškovi dostave teret ( Z), što odgovara optimalnom planu koji smo pronašli, prema formuli:

Zmin = 10 ∙ 1 + 15 ∙ 3 + 5 ∙ 2 + 15 ∙ 1 + 15 ∙ 2 = 110 den. jedinice

Ukupni troškovi dostave za sve proizvode, za optimalno rješenje, šminkati se 110 jazbina jedinice

10. Konstrukcija transportnog grafa

Pronašavši optimalan plan prijevoza, mi ćemo konstruirati. Vrhovi grafa bit će "skladišta" i "trgovine". Na vrhovima označavamo odgovarajuće količine rezervi i potreba. Lukovi koji povezuju vrhove grafa odgovarat će transportima različitim od nule. Potpisat ćemo svaki takav luk, navodeći količinu prevezenog tereta.

Rezultat će biti grafikon sličan onom prikazanom u nastavku:

To je to, problem transporta riješen. čestitamo!

Praktična primjena transportnog problema

Transportni problem se koristi u mnogim slučajevima. Ovo je optimizacija opskrbe sirovinama i zalihama proizvodna poduzeća. Radi se o optimizaciji isporuke robe iz skladišta u maloprodaju. To je optimizacija prijevoza putnika i još puno, puno više.

Galyautdinov R.R.

© Kopiranje materijala dopušteno je samo uz izravnu hipervezu na

Predznak optimalnosti referentnog plana

Ako su u simpleks tablici koja sadrži određeni plan podrške svi elementi f-reda (osim slobodnog člana) nenegativni, tada je ovaj plan podrške optimalan. Neka u f-redu tablice. 2.b 0j > (i=1, ..., n m). U referentnom planu x 0 sadržanom u ovoj tablici, vrijednosti svih slobodnih varijabli x m+j jednake su nuli i f(x 0) =b 00. Ako povećate bilo koju od slobodnih varijabli x m+ j, tada će se, kao što se vidi iz jednakosti (2.5), zbog nenegativnosti b 0j, vrijednost f(x) početi smanjivati. Posljedično, pri x o funkcija f(x) postiže svoju najveću vrijednost, što znači da je x 0 doista optimalni referentni plan.

Sposobnost prelaska s jednog referentnog plana na drugi

Kao što je gore spomenuto, bit simpleks metode je u procesu dokazivanja sljedećeg kriterija: ako u f-retku simpleks tablice koja sadrži neki referentni plan postoji barem jedan negativan element (ne računajući slobodni član), koji odgovara stupcu s barem jednim pozitivnim elementom, tada možete transformacijom baze prijeći na drugi referentni plan s većom vrijednošću funkcije cilja.

Dokažimo ovaj znak. Uspostavimo pravila za odabir varijabli za takvu transformaciju početne baze B o s referentnim planom x 0 u nova osnova B 1 s referentnim planom x 1 u kojem; vrijednost funkcije f raste, tj. f(x i)>f(x 0). Zatim, prema pravilu za preračunavanje elemenata iz simpleks tablice, transformiramo ih na novu osnovu, što će nam omogućiti pronalaženje komponenti novog referentnog plana.

Pretpostavimo da u tablici. 2.1, na primjer, b 0s<0, а среди элементов b is s-го столбца есть хотя бы один положительный. Полагая в равенстве (2.5) все свободные переменные х m+j кроме x m+s , равными нулю, получаем f = b oo -- b os xm+s . Из этого равенства видно, что при увеличении x m+s значение f тоже возрастает. Таким образом, при указанных в признаке условиях действительно есть возможность увеличить f(x), переходя к планам, в которых x m+s принимает положительные значения, а все остальные компоненты x m+j по-прежнему равны нулю. Покажем, что среди таких планов существует и опорный. Тем самым будет найден путь направленного преобразования базиса Б о в новый базис Б 1 . В самом деле, если переменная x m+s принимает положительное значение в некотором опорном плане, значит, она является в нем базисной компонентой (в опорном плане x о она была свободной компонентой и равнялась нулю). Поэтому прежний базис следует преобразовать за счет включения в него переменной x m+s . Но здесь предстоит решить два вопроса:

1) koju od varijabli treba ukloniti iz prethodne baze da bi se napravilo mjesta za varijablu x m+s;

2) koju vrijednost treba imati nova osnovna varijabla x m+s u novom referentnom planu.

Da bismo riješili postavljena pitanja, pretpostavimo da su u jednakosti (2.4) svi x m+j, osim x m+s, jednaki nuli. Zatim

x i = b io -b je x m+s (i=l, ..., m)

Iz ovih jednakosti jasno je da s porastom x m+s vrijednosti onih osnovnih varijabli x i za koje su koeficijenti b<0, тоже будут расти, оставаясь положительными. Значит, на отрицательные коэффициенты b is можно внимания не обращать, так как они не влияют на знак базисных переменных. Иначе обстоит дело с базисными переменными, у которых b is >0. Kako x m+s raste, tako će se vrijednosti ovih varijabli početi smanjivati ​​i doći će trenutak nakon kojeg će one poprimiti negativne vrijednosti i uvjet (2.3) više neće biti zadovoljen. Ovo se ne može dopustiti. Dakle, otkrijmo do koje se granične vrijednosti x m+s može povećati bez narušavanja uvjeta nenegativnosti osnovnih varijabli. U tu svrhu ispišemo iz sustava (2.6) one jednakosti u kojima je b >0. Pretpostavimo da se radi o jednakostima s brojevima i=d,…,k,…,p:

x d =b do -- b ds x m+s ,

…………………..

x k =b k0 - b ks x m+s ,

………………….

x p =b p0 - b ps x m+s .

Osnovne varijable x d, ..., x k, ..., x p ostat će nenegativne sve dok x m+s zadovoljava sustav nejednakosti

b do - b ds x m+s >0, x m+s

……………… ………………

b k0 - b ks x m +s >0 ili x m+s< b ko /b ks

……………… ………………

b p0 - b ps x m+s >0 x m+s< b po /b ps

tj. u x m+s

Neka najmanji od razlomaka b io /b is odgovara i = k, tj.

min ( b io /b je )= b k0 /b ks .

Tada možemo reći da sve dok x m+s ne prelazi vrijednost b k0 /b ks , tj. x m+s 0, tada će varijabla x k postati jednaka metku: x k = b k0 -- b ks b ko /b ks =0, a time će se baza transformirati B o = (x 1 ; ...; x k ; . ..; x m ) u novu bazu, u kojoj varijabla x m+s prelazi iz slobodne grupe u osnovnu, a varijabla x k zauzima mjesto x m+s u slobodnoj grupi. Pritom su sve ostale slobodne varijable i dalje jednake nuli, a preostale osnovne varijable su i dalje pozitivne. Prema tome, osnovni plan x 1 u novoj bazi B 1 = (x 1 ; ...; x m+s ; ...; x m ) imat će m pozitivnih komponenti i m-n nula jedinica. U planu x 1, neke osnovne varijable mogu poprimiti nulte vrijednosti u dva slučaja:

1) kada u planu x 0 postoje osnovne varijable jednake nuli;

2) kada najmanji od razlomaka b io /b odgovara dvama ili više brojeva i. U našem slučaju odgovara samo i = k.

Varijabla koja se uključuje u bazu određena je negativnim elementom f-niza. Iz jednakosti f =b oo - b os x m+s jasno je da kada je b 0s<0 и фиксированном x m+s >0, vrijednost f(x) ovisi o apsolutnoj vrijednosti koeficijenta b 0s: što je veći |b 0s |, to će vrijednost f(x) dobiti veću u novoj bazi. Ali iz ove jednakosti također je jasno da vrijednost funkcije cilja u novoj bazi također ovisi o vrijednosti koju preuzima nova bazna varijabla x m+s. Odabrat ćemo varijablu uvedenu u bazu, fokusirajući se samo na negativne elemente f-reda. Dakle, kada postoji više negativnih elemenata u f-retku, u bazu ćemo uvesti varijablu x m+j koja odgovara negativnom elementu najveće apsolutne vrijednosti. Stupac koeficijenata za varijablu uključenu u bazu naziva se razrješenje. Dakle, odabirom varijable uvedene u bazu (ili odabirom razrješujućeg stupca) na temelju negativnog elementa f-reda, osiguravamo da funkcija f raste.

Malo je teže odrediti varijablu koju treba isključiti iz osnovice. Da bi to učinili, sastavljaju omjere slobodnih članova prema pozitivnim elementima razlučivačkog stupca (takve se relacije nazivaju simpleks) i pronalaze najmanji među njima, koji određuje red (razrješavanje) koji sadrži isključenu varijablu. Izbor varijable isključene iz baze (ili izbor razlučive linije) prema minimalnoj simpleks relaciji jamči pozitivnost komponenti baze u novom referentnom planu.

Dakle, dokazali smo da je pod uvjetima navedenim u znaku doista moguće prijeći s jednog referentnog plana na drugi s velikom vrijednošću funkcije cilja f(x).

Imajte na umu da već znamo vrijednost nove bazne varijable x m+s u novom referentnom planu: ona je jednaka b ko /b ks . Što se tiče numeričkih vrijednosti preostalih osnovnih varijabli u novom referentnom planu i pripadajuće vrijednosti f(x), one se mogu pronaći tek nakon promijenjenog sustava osnovnih varijabli x 1 ;..., x m+s ; ...,x m će se izraziti kroz modificirani sustav slobodnih varijabli x m+1,…,x k,…, x n. Da bismo to učinili, postavimo; pravila po kojima se uvjeti problema transformiraju iz jedne osnove u drugu.

Koeficijent b ks = 0 pri x m+s u ovoj se jednadžbi naziva razlučnim elementom. U jednakosti (2.7) nova osnovna varijabla x m+s izražena je preko slobodnih varijabli, među kojima se sada nalazi dosadašnja osnovna varijabla x k. Tako su varijable x m+s i x k zamijenile uloge.

Izrazimo na sličan način preostale osnovne varijable kroz novi skup slobodnih varijabli. U tu svrhu zamijenimo vrijednost x m+s iz preostalih jednakosti (označimo f s x 0, tada će jednakost biti uključena u sustav pri i = 0)

Dovođenje sustava na novu osnovu naziva se simpleks transformacija. Ako se simpleks transformacija promatra kao formalna algebarska operacija, tada se može primijetiti da se kao rezultat ove operacije preraspodjeljuju uloge između dviju varijabli uključenih u određeni sustav linearnih funkcija: jedna varijabla prelazi iz zavisne u nezavisnu, a druga , naprotiv, od neovisnog prema ovisnom . Ova operacija je u algebri poznata kao Jordanov korak eliminacije.

123 stranice (Word datoteka)

Pogledaj sve stranice

Fragment teksta djela

Prijelaz s jednog referentnog plana na drugi, u kojem je vrijednost ciljne funkcije veća nego u prethodnom.

3. Provjera optimalnosti dobivenog plana, što vam omogućuje da odmah zaustavite traženje referentnih planova ili donesete zaključak da ne postoji optimalan plan.

Simpleks metoda temelji se na sljedećim teoremima, koji su dani bez dokaza.

Teorem 1.2 (o postojanju plana potpore)

Ako je linearna forma ograničena odozgo na nepraznom skupu D, tada je LLP rješiv, to jest, postoji točka takva da .

Teorem 1.3 (test optimalnosti plana potpore)

Osnovni plan problem (1.18) je optimalan ako za sve j , je zadovoljan, gdje je količina

(1.21)

nazvao simpleks - razlika ili procjena.

Teorem 1.4 (test nepostojanja optimalnog plana)

Ako za neki k i među brojevima , nema pozitivnih, tj. Sve u svemu, ciljna funkcija problema nije ograničena na skup izvedivih rješenja i nema konačno rješenje.

Teorem 1.5 (test za postojanje boljeg plana podrške)

Ako referentni plan problem (1.18) nije degeneriran za neko k, ali među brojevima postoji barem jedan pozitivan, tj. ne sve, onda postoji referentni plan , u kojem funkcija cilja ima vrijednost ne manju nego u prethodnom planu: .

Algoritam Simplex metode

1. Problem se mora svesti na kanonski oblik. Sustav ograničenja sveden je na jediničnu osnovu, tj. rješava se s obzirom na neke osnovne varijable (bez gubitka općenitosti, pretpostavit ćemo da s obzirom na prvih m varijabli) pomoću Jordan–Gaussove metode (sustav (1.19)). Dobije se odgovarajuća početna referentna otopina.

2. Radi lakšeg izračuna sve zapisujemo u simpleks tablicu (tablica 1.1). Stupac Basis sadrži popis osnovnih varijabli; sljedeći stupac “c j baza” sadrži koeficijente funkcije cilja za bazne varijable; sljedeći stupci sadrže koeficijente sustava ograničenja za odgovarajuće varijable; stupac “b i” je stupac slobodnih članova sustava ograničenja. Zadnji redak sadrži simpleks - razlike izračunate pomoću formule (1.21), a zadnja ćelija sadrži vrijednost funkcije cilja =. Imajte na umu da je simpleks – razlika osnovnih varijabli – uvijek jednak nuli.

Tablica 1.1

		c j osnovica

3. Ako je sve simplex, razlike su nenegativne, tj. , tada je referentni plan optimalan.

4. Ako je barem jedna simpleks - razlika negativna, , au odgovarajućem stupcu nema pozitivnih elemenata, tada problem nema optimalno rješenje, tj. .

5. Ako je barem jedna simpleks - razlika negativna, , au svakom stupcu koji ima negativnu ocjenu postoji barem jedan pozitivan element, tada se dobiveni referentni plan može poboljšati.

6. Odaberite omogućiti stupac“p”, što odgovara najmanjem negativnom rezultatu.

7. Odaberite niz dopuštenja"k", što odgovara najmanjem omjeru desnih strana prema odgovarajućim pozitivnim elementima stupca rezolucije. Poziva se element na sjecištu stupca rezolucije i retka rezolucije permisivni element.

8. Prelazimo na novu simplex tablicu, u kojoj će biti nova baza: osnovna varijabla na “k” mjestu u staroj bazi mijenja se u novu varijablu. Odgovarajući vektor nove bazne varijable mora se pretvoriti u jedinični. Da biste to učinili, podijelite liniju razlučivosti s tako da se jedinica pojavi na mjestu elementa razlučivosti. Množenjem linije rezolucije s odgovarajućim brojevima i zbrajanjem s ostalim linijama, dobivamo nule u stupcu rezolucije. Nakon toga ispisujemo novi referentni plan i preračunavamo liniju predračuna. Prijeđimo na točku 3.

Napomena o alternativnom planu.

Ako se sve procjene slobodnih varijabli u posljednjoj simpleks tablici pokažu striktno većim od nule, tada je optimalni plan jedinstven. Ako je barem jedna procjena za slobodnu varijablu jednaka nuli, tada postoji alternativni optimum (skup optimalnih planova). Da bi se pronašlo alternativno rješenje, potrebno je poduzeti jedan korak simpleks metode, odabirući kao razlučujući stupac slobodnu varijablu, koja odgovara nultom rezultatu.

U ovom slučaju, skup svih optimalnih planova može se predstaviti kao konveksna linearna kombinacija nosećih optimalnih planova: , Gdje .

Primjer 5. Riješite ZLP koristeći simpleks metodu:

(1.22)

Sustav linearnih nejednadžbi (1.22) svodimo na kanonski oblik uvođenjem dodatne nenegativne varijable u svaku nejednadžbu. Dobivamo sustav linearnih jednadžbi:

(1.23)

Ciljna funkcija će imati oblik

Kreiramo simplex tablicu:

Tablica 1.2

		c j osnovica

Osnovni plan nije optimalan, jer u retku ocjena nalaze se negativni elementi = - 3 i = - 2. Odabiremo razrješavajući stupac - prvi, jer odgovara minimumu negativnih ocjena = - 3. Za sve pozitivne elemente prvog stupca izračunavamo omjer . Nalazimo minimalni od ovih omjera: . Odgovara drugom retku, stoga će biti permisivan. Dakle, razlučni element pokazuje da je varijabla x 4 izvedena iz baze, a umjesto nje će u bazi biti varijabla x 1. Ispunjavamo novu simplex tablicu (tablica 1.3). Da bismo to učinili, pretvaramo prvi stupac u jedan stupac. Drugi red pomnožimo s (-1/2) i zbrojimo s prvim, rezultat upišemo u prvi redak nove simpleks tablice; na sličan način pomnožite drugi redak s (1/2) i dodajte ga trećem; podijelite liniju rezolucije s 2; Četvrti prepisujemo bez promjena.