Grafičkom metodom za rješavanje LP zadataka, zapravo smo iz skupa vrhova koji pripadaju granici skupa rješenja sistema nejednačina izabrali onaj vrh na kojem je vrijednost ciljne funkcije dostigla maksimum (minimum). U slučaju dvije varijable, ova metoda je prilično jasna i omogućava vam da brzo pronađete rješenje problema.
Ako u problemu postoje tri ili više varijabli, a to je upravo situacija u stvarnim ekonomskim problemima, teško je vizualizirati područje rješenja za sistem ograničenja. Takvi zadaci se rješavaju uz pomoć simpleks metoda ili metodu uzastopnih poboljšanja. Ideja metode je jednostavna i sastoji se u sljedećem.
Prema određenom pravilu, pronalazi se početni referentni plan (neki vrh područja ograničenja). Provjerava se da li je plan optimalan. Ako da, onda je problem riješen. Ako ne, onda prelazimo na drugi poboljšani plan - na drugi vrh. vrijednost funkcije cilja na ovom planu (na ovom vrhu) je svakako bolja nego na prethodnom. Algoritam tranzicije se izvodi uz pomoć nekog računskog koraka, koji je zgodno zapisan u obliku tablica tzv. simpleks stolovi . Kako postoji konačan broj vrhova, u konačnom broju koraka dolazimo do optimalnog rješenja.
Razmotrimo simpleks metodu na konkretnom primjeru zadatka izrade plana.
Još jednom napominjemo da je simpleks metoda primjenjiva na rješavanje kanonskih LP problema svedenih na poseban oblik, tj. da imaju osnovu, pozitivne desne strane i ciljnu funkciju izraženu u terminima nebazičnih varijabli. Ako se problem ne svodi na poseban oblik, tada su potrebni dodatni koraci o kojima ćemo kasnije razgovarati.
Razmotrimo problem plana proizvodnje, nakon što smo prethodno izgradili model i sveli ga na poseban oblik.
Zadatak.
Za proizvodnju proizvoda ALI I IN skladište može osloboditi sirovine ne više od 80 jedinica. I za proizvodnju proizvoda ALI dvije jedinice se troše i proizvodi IN- jedna jedinica sirovine. Potrebno je planirati proizvodnju tako da se osigura najveći profit ako proizvodi ALI potrebno je proizvesti najviše 50 komada i proizvoda IN- ne više od 40 kom. Štaviše, profit od prodaje jednog proizvoda ALI- 5 rubalja, i od IN- 3 rub.
Konstruirajmo matematički model, označavajući X 1 broj proizvoda A u smislu X 2 - broj proizvoda IN. tada će sistem ograničenja izgledati ovako:
Dovedemo problem u kanonski oblik uvođenjem dodatnih varijabli:
(3.10)
F = -5x 1 - 3x 2 → min.
Ovaj problem ima poseban oblik (sa osnovom, desne strane su nenegativne). Može se riješiti simpleks metodom.
Ipozornici. Pisanje zadatka u simpleks tablicu. Postoji korespondencija jedan-na-jedan između sistema ograničenja problema (3.10) i simpleks tabele. U tabeli ima onoliko redova koliko ima jednakosti u sistemu ograničenja i onoliko kolona koliko ima slobodnih varijabli. Osnovne varijable ispunjavaju prvu kolonu, slobodne varijable popunjavaju gornji red tabele. Donja linija se zove indeksna linija i sadrži koeficijente za varijable u funkciji cilja. U donjem desnom uglu, 0 je inicijalno napisano ako u funkciji nema slobodnog člana; ako postoji, onda ga pišemo sa suprotnim predznakom. Na ovom mjestu (u donjem desnom kutu) nalazit će se vrijednost funkcije cilja, koja bi trebala rasti po modulu pri prelasku s jedne tabele na drugu. Dakle, naš sistem ograničenja odgovara tabeli 3.4 i možemo prijeći na drugu fazu rješenja.
Tabela 3.4
|
osnovni |
besplatno |
||
IIpozornici. Provjera optimalnosti osnovnog plana.
Ova tabela 3.4 odgovara sljedećoj osnovnoj liniji:
(X 1 , X 2 , X 3 , X 4 , X 5) = (0, 0, 50, 40, 80).
Slobodne varijable X 1 , X 2 su 0; X 1 = 0, X 2 = 0. I osnovne varijable X 3 , X 4 , X 5 uzimaju vrijednosti X 3 = 50, X 4 = 40, X 5 = 80 - iz kolone slobodnih članova. Vrijednost funkcije cilja:
-F = - 5X 1 - 3X 2 = -5 0 - 3 0 = 0.
Naš zadatak je provjeriti da li je dati osnovni plan optimalan. da biste to učinili, trebate pogledati liniju indeksa - liniju funkcije cilja F.
Moguće su različite situacije.
1. U indeksu F-string nema negativnih elemenata. Dakle, plan je optimalan, možemo napisati rješenje problema. Ciljna funkcija je dostigla svoju optimalnu vrijednost, jednaku broju u donjem desnom uglu, uzetom sa suprotnim predznakom. Pređimo na fazu IV.
2. U retku indeksa postoji najmanje jedan negativan element, u čijoj koloni nema pozitivnih. Tada zaključujemo da je funkcija cilja F→∞ se neograničeno smanjuje.
3. U retku indeksa postoji negativan element čija kolona sadrži najmanje jedan pozitivan element. Zatim prelazimo na sljedeću III fazu. ponovo izračunati tabelu, poboljšavajući osnovnu liniju.
IIIpozornici. Poboljšanje osnovnog plana.
Od negativnih elemenata indeksa F-redove biramo najveći modul, kolonu koja mu odgovara nazivamo razrješenjem i označavamo "".
Da biste odabrali razrješavajući red, potrebno je izračunati omjere elemenata kolone slobodnih članova samo to pozitivno elementi stupca dozvole. Od dobijenih omjera odaberite minimum. Odgovarajući element na kojem se postiže minimum naziva se razlučujući element. Istaknut ćemo ga kvadratom.
U našem primjeru, 
, element 2 - permisivan. Niz koji odgovara ovom elementu naziva se i rješavanje (tabela 3.5).
Tabela 3.5
Nakon što smo odabrali razrješavajući element, ponovo izračunavamo tablicu prema pravilima:
1. U novoj tabeli iste veličine kao i ranije, varijable za razrješenje reda i stupca se zamjenjuju, što odgovara prijelazu na novu osnovu. U našem primjeru: X 1 je uključen u osnovicu, umjesto X 5, koji napušta osnovu i sada je slobodan (Tablica 3.6).
Tabela 3.6
|
osnovni |
besplatno |
||
2. Umjesto rezolucionog elementa 2, zapisujemo njegovu recipročnu vrijednost.
3. Podijelite elemente permisivne linije sa permisivnim elementom.
4. Elementi kolone za razrješenje podijeljeni su elementom za razrješenje i napisani su suprotnim predznakom.
5. Da bismo popunili preostale elemente tabele 3.6, vršimo preračunavanje prema pravilu pravougaonika. Recimo da želimo izbrojati element na mjestu 50.
Mi mentalno povezujemo ovaj element s onim koji razrješava, pronalazimo proizvod, oduzimamo proizvod elemenata koji se nalaze na drugoj dijagonali rezultirajućeg pravokutnika. Razlika je podijeljena elementom za razrješenje.
Dakle, . Pišemo 10 na mjestu gdje je bilo 50. Slično :
, 
, , 
.
Tabela 3.7
Imamo novu tabelu 3.7, osnovne varijable su sada varijable (x 3 ,x 4 ,x 1 ). Vrijednost funkcije cilja postala je jednaka -200, odnosno smanjila se. Da bismo provjerili optimalnost ovog osnovnog rješenja, moramo se vratiti na fazu II. Proces je očigledno konačan, kriterijum zaustavljanja su tačke 1 i 2 faze II.
Hajde da dovršimo rješenje problema. Da biste to učinili, provjerite red indeksa i, ugledajući negativan element u njemu, pozovite kolonu koja mu odgovara razrješavanjem i, prema fazi III, ponovo izračunajte tablicu. Nakon što smo napravili omjere i odabrali između njih minimum = 40, odredili smo razlučujući element 1. Sada se ponovno izračunavanje vrši prema pravilima 2-5.
Tabela 3.8
|
osnovni |
besplatno |
||
|
x 3 = 30, X 2 = 40, X 1 = 20. Slobodne varijable su 0, X 5 = 0, X 4 = 0. Funkcija cilja uzima vrijednost posljednjeg elementa kolone slobodnih pojmova suprotnog predznaka: - F = -220 F = 220, u našem primjeru funkcija je ispitana za min, i inicijalno F max, tako da se znak zapravo dvaput promijenio. dakle, X* = (20, 40, 30, 0, 0), F* = 220. Odgovor na problem: U plan izdavanja potrebno je uključiti 20 proizvoda tog tipa ALI, 40 proizvoda tipa B, dok će profit biti maksimalan i iznosit će 220 rubalja. Na kraju ovog odjeljka dajemo dijagram toka algoritma simpleks metode, koji tačno ponavlja korake, ali, možda će nekim čitateljima biti prikladniji za korištenje, jer strelice pokazuju jasan smjer djelovanja. Veze iznad okvira u dijagramu toka pokazuju kojem koraku ili podstavci pripada odgovarajuća grupa transformacija. pravilo za pronalaženje početne osnovne linije biće formulisano u paragrafu 3.7.
Pitanja za samokontrolu 1. Kako se konstruiše simpleks tabela? 2. Kako se promjena osnove odražava u tabeli? 3. Formulirajte kriterij zaustavljanja za simpleks metodu. 4. Kako organizovati preračunavanje tabele? 5. Sa koje linije je zgodno započeti preračunavanje tabele? |
. Simpleks metodski algoritam
Primjer 5.1. Riješite sljedeći problem linearnog programiranja korištenjem simpleks metode:
Rješenje:
I iteracija:
x3, x4, x5, x6 x1,x2. Osnovne varijable izražavamo u terminima slobodnih:
Ciljnu funkciju dovodimo u sljedeći oblik:
Na osnovu dobijenog problema formiraćemo početnu simpleks tabelu:
Tabela 5.3
Inicijalna simpleks tabela
Procijenjeni 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 sistema ograničenja LLP.
Na ovoj iteraciji (u tabeli 5.3) nije otkriven znak nekonzistentnosti sistema ograničenja (osobina 1) (tj. ne postoji linija sa negativnim slobodnim brojem (osim linije ciljne funkcije) koja ne sadrži najmanje jedan negativni element (tj. negativan koeficijent za slobodnu varijablu)).
Na ovoj iteraciji (u tabeli 5.3) nije otkriven znak neograničenosti funkcije cilja (znak 2) (tj. nema stupca sa negativnim elementom u liniji funkcije cilja (osim kolone slobodnih brojeva) u kojoj 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.
Pronađeno osnovno rješenje nije optimalno, jer prema kriteriju optimalnosti (znak 4) u liniji funkcije cilja ne bi trebalo biti negativnih elemenata (slobodni broj ove prave se ne uzima u obzir pri razmatranju ovog znaka ). Stoga, prema algoritmu simpleks metode, prelazimo na 8. fazu.
Pošto je pronađeno osnovno rješenje prihvatljivo, razlučuju kolonu ćemo tražiti po sljedećoj shemi: kolone sa negativnim elementima određujemo u liniji funkcije cilja (osim kolone slobodnih brojeva). Prema tabeli 5.3, postoje dvije takve kolone: kolona " x1" i kolona " x2". Iz takvih kolona bira se onaj koji sadrži najmanji element u liniji funkcije cilja. Ona će se rešiti. Kolona " x2' sadrži najmanji element (-3) u poređenju sa stupcem ' x1
Da bismo odredili permisivni niz, nalazimo pozitivne procijenjene omjere slobodnih brojeva prema elementima dopuštenog stupca, niz koji odgovara najmanjem pozitivnom procijenjenom omjeru uzima se kao dozvoljen.
Tabela 5.4
Inicijalna simpleks tabela
U tabeli 5.4 najmanji pozitivni koeficijent evaluacije odgovara liniji " x5“, dakle, bit će riješeno.
Element koji se nalazi na raskrsnici omogućavajuće kolone i omogućavajuće linije se prihvata kao omogućavajući. U našem primjeru, ovo je element koji se nalazi na presjeku linije " x5» i stupci « x2».
Element za razrješavanje prikazuje jednu osnovnu i jednu slobodnu varijablu koje je potrebno zamijeniti u simpleks tablici da bi se prešlo na novo „poboljšano“ osnovno rješenje. U ovom slučaju, to su varijable. x5 I x2, u novoj simpleks tabeli (tabela 5.5) mijenjamo ih.
9.1. Dozvoli transformaciju elementa.
Dozvoljeni element tabele 5.4 transformiše se na sledeći način:
Dobiveni rezultat unosimo u sličnu ćeliju u tablicu 5.5.
9.2. Dozvoli konverziju nizova.
Elementi permisivne linije tabele 5.4 podeljeni su permisivnim elementom ove simpleks tabele, rezultati se uklapaju u slične ćelije nove simpleks tabele (tabela 5.5). Transformacije elemenata niza omogućavanja date su u tabeli 5.5.
9.3. Dozvoljena transformacija stupca.
Elementi razlučujuće kolone tabele 5.4 podijeljeni su razlučivim elementom ove simpleks tablice, a rezultat se uzima sa suprotnim predznakom. Dobijeni rezultati uklapaju se u slične ćelije nove simpleks tabele (tablice 5.5). Transformacije elemenata kolone za razrješenje date su u tabeli 5.5.
9.4. Transformacija preostalih elemenata simpleks tabele.
Transformacija ostalih elemenata simpleksne tabele (tj. elemenata koji se ne nalaze u razlučujućem redu i razlučujućem stupcu) vrši se prema pravilu "pravougaonika".
Na primjer, razmotrite transformaciju elementa koji se nalazi na presjeku niza " x3” i kolone “”, uslovno označavaju kao “ x3". U tabeli 5.4 mentalno crtamo pravougaonik, čiji se jedan vrh nalazi u ćeliji, čija se vrednost transformiše (tj. u ćeliji " x3”), a drugi (dijagonalni vrh) je u ćeliji sa elementom za razrješenje. Druga dva vrha (druge dijagonale) su jednoznačno određena. Zatim transformirana vrijednost ćelije " x3"biće jednak prethodnoj vrijednosti ove ćelije minus razlomak, u čijem nazivniku je razlučujući element (iz tabele 5.4), a u brojniku proizvod dva druga neiskorištena vrha, tj.:
« x3»: .
Vrijednosti ostalih ćelija se pretvaraju na sličan način:
« x3 x1»: ;
« x4»: 
;
« x4 x1»: ;
« x6»: 
;
« x6 x1»: ;
«»: 
;
« x1»: 
.
Kao rezultat ovih transformacija, dobijena je nova simpleks tablica (tabela 5.5).
II iteracija:
Faza 1: sastavljanje simpleks tabele.
Tabela 5.5
Simpleks stolII iteracije
Procijenjeno odnosi |
||||
| ||||
|
|
Faza 2: određivanje osnovnog rješenja.
Kao rezultat simpleks transformacija, dobijeno je novo osnovno rješenje (tabela 5.5):
Kao što vidite, kod ovog osnovnog rješenja vrijednost ciljne funkcije =15, što je više nego kod prethodnog osnovnog rješenja.
Nije utvrđena nedosljednost sistema ograničenja u skladu sa znakom 1 u tabeli 5.5.
Faza 4: provjeravanje ograničenosti ciljne funkcije.
Neograničenost funkcije cilja u skladu sa predznakom 2 u tabeli 5.5 nije otkrivena.
Faza 5: provjera prihvatljivosti pronađenog osnovnog rješenja.
Pronađeno osnovno rješenje u skladu sa obilježjem 4 nije optimalno, jer linija ciljne funkcije simpleks tablice (tabela 5.5) sadrži negativan element: -2 (slobodni broj ove linije se ne uzima u obzir pri razmatranju ovog karakteristika). Dakle, idemo na korak 8.
Faza 8: definicija elementa koji omogućava.
8.1. Definicija stupca rezolucije.
Pronađeno osnovno rješenje je prihvatljivo, kolone sa negativnim elementima određujemo u liniji funkcije cilja (osim kolone slobodnih brojeva). Prema tabeli 5.5, postoji samo jedna takva kolona: " x1". Stoga ga prihvatamo kao dozvoljeno.
8.2. Definicija dopuštajućeg niza.
Prema dobijenim vrijednostima pozitivnih procijenjenih omjera u tabeli 5.6, minimalni je omjer koji odgovara liniji " x3". Stoga ga prihvatamo kao dozvoljeno.
Tabela 5.6
Simpleks stolII iteracije
Procijenjeno odnosi |
||||
3/1=3 – min |
||||
Faza 9: transformacija simpleks tablice.
Transformacije simpleks tabele (tabela 5.6) se izvode na isti način kao u prethodnoj iteraciji. Rezultati transformacija elemenata simpleks tablice prikazani su u tabeli 5.7.
III iteracija
Na osnovu rezultata simpleks transformacije prethodne iteracije, sastavljamo novu simpleks tablicu:
Tabela 5.7
Simpleks stolIII iteracije
Procijenjeno odnosi |
||||
| ||||
|
|
Faza 2: određivanje osnovnog rješenja.
Kao rezultat simpleks transformacija, dobijeno je novo osnovno rješenje (tabela 5.7):
Faza 3: provjera kompatibilnosti sistema ograničenja.
Nije utvrđena nedosljednost sistema ograničenja u skladu sa znakom 1 u tabeli 5.7.
Faza 4: provjeravanje ograničenosti ciljne funkcije.
Neograničenost funkcije cilja u skladu sa predznakom 2 u tabeli 5.7 nije otkrivena.
Faza 5: provjera prihvatljivosti pronađenog osnovnog rješenja.
Pronađeno osnovno rješenje u skladu sa kriterijem 3 je prihvatljivo, jer ne sadrži negativne komponente.
Faza 6: provjera optimalnosti pronađenog osnovnog rješenja.
Pronađeno osnovno rješenje prema osobini 4 nije optimalno, jer linija ciljne funkcije simpleks tablice (tabela 5.7) sadrži negativan element: -3 (slobodni broj ove linije se ne uzima u obzir pri razmatranju ovog karakteristika). Dakle, idemo na korak 8.
Faza 8: definicija elementa koji omogućava.
8.1. Definicija stupca rezolucije.
Pronađeno osnovno rješenje je prihvatljivo, kolone sa negativnim elementima određujemo u liniji funkcije cilja (osim kolone slobodnih brojeva). Prema tabeli 5.7, postoji samo jedna takva kolona: " x5". Stoga ga prihvatamo kao dozvoljeno.
8.2. Definicija dopuštajućeg niza.
Prema dobijenim vrijednostima pozitivnih procijenjenih omjera u tabeli 5.8, minimalni je omjer koji odgovara liniji " x4". Stoga ga prihvatamo kao dozvoljeno.
Tabela 5.8
Simpleks stolIII iteracije
Procijenjeno odnosi |
||||
5/5=1 – min |
||||
Faza 9: transformacija simpleks tablice.
Transformacije simpleks tabele (tabela 5.8) se izvode na isti način kao u prethodnoj iteraciji. Rezultati transformacija elemenata simpleks tablice prikazani su u tabeli 5.9.
IV iteracija
Faza 1: izgradnja novog simplex stola.
Na osnovu rezultata simpleks transformacije prethodne iteracije, sastavljamo novu simpleks tablicu:
Tabela 5.9
Simpleks stolIV iteracije
Procijenjeno odnosi |
||||
| –(–3/5)=3/5 | |||
–(1/5)=–1/5 | ||||
| –(9/5)=–9/5 | |||
|
| –(–3/5)=3/5 |
Faza 2: određivanje osnovnog rješenja.
Kao rezultat simpleks transformacija dobijeno je novo osnovno rješenje, prema tabeli 5.9, rješenje je sljedeće:
Faza 3: provjera kompatibilnosti sistema ograničenja.
Nije otkrivena nedosljednost sistema ograničenja u skladu sa obilježjem 1 u tabeli 5.9.
Faza 4: provjeravanje ograničenosti ciljne funkcije.
Neograničenost funkcije cilja u skladu sa predznakom 2 u tabeli 5.9 nije otkrivena.
Faza 5: provjera prihvatljivosti pronađenog osnovnog rješenja.
Pronađeno osnovno rješenje u skladu sa kriterijem 3 je prihvatljivo, jer ne sadrži negativne komponente.
Faza 6: provjera optimalnosti pronađenog osnovnog rješenja.
Osnovno rješenje pronađeno u skladu sa obilježjem 4 je optimalno, jer u redu ciljne funkcije simpleksne tablice nema negativnih elemenata (tabela 5.9) (slobodni broj ovog reda se ne uzima u obzir pri razmatranju ove karakteristike) .
Faza 7: provjera alternativnog rješenja.
Pronađeno rješenje je jedino, jer u liniji funkcije cilja nema nultih elemenata (tabela 5.9) (slobodni broj ove linije se ne uzima u obzir pri razmatranju ove karakteristike).
odgovor: optimalna vrijednost ciljne funkcije problema koji se razmatra =24, što se postiže pri.
Primjer 5.2. Riješite gornji problem linearnog programiranja pod pretpostavkom da je ciljna funkcija minimizirana:
Rješenje:
I iteracija:
Faza 1: formiranje početne simpleks tablice.
Originalni problem linearnog programiranja dat je u standardnom obliku. Dovedemo ga u kanonski oblik uvođenjem dodatne nenegativne varijable u svako od ograničenja nejednakosti, tj.
U rezultirajućem sistemu jednačina uzimamo kao dozvoljene (osnovne) varijable x3, x4, x5, x6, tada su slobodne varijable x1,x2. Osnovne varijable izražavamo u terminima slobodnih.
| - | x 1 | + | x2 | - | S1 | = | 1 | ||||||||||
| x 1 | +3 | x2 | + | S2 | = | 15 | |||||||||||
| - | 2 | x 1 | + | x2 | + | S3 | = | 4 |
| - | x 1 | + | x2 | - | S1 | + | R1 | = | 1 | |||||||||||
| x 1 | +3 | x2 | + | S2 | = | 15 | ||||||||||||||
| - | 2 | x 1 | + | x2 | + | S3 | = | 4 |
| x 1 = 0 x 2 = 0 S 1 = 0 S 2 = 15 S 3 = 4 R 1 = 1 |
=>W=1 |
| x 1 | x2 | S1 | S2 | S3 | R1 | Sv. član | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | 1: 1 = 1 |
| 1 | 3 | 0 | 1 | 0 | 0 | 15 | 15: 3 = 5 |
| -2 | 1 | 0 | 0 | 1 | 0 | 4 | 4: 1 = 4 |
| 1 | -1 | 1 | 0 | 0 | 0 | Ž - 1 | |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | |
| 4 | 0 | 3 | 1 | 0 | -3 | 12 | |
| -1 | 0 | 1 | 0 | 1 | -1 | 3 | |
| 0 | 0 | 0 | 0 | 0 | 1 | Ž - 0 |
| - | x 1 | + | x2 | - | S1 | = | 1 | ||||||||||
| 4 | x 1 | + | 3 | S1 | + | S2 | = | 12 | |||||||||
| - | x 1 | + | S1 | + | S3 | = | 3 |
| x 1 | x2 | S1 | S2 | S3 | Sv. član | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 4 | 0 | 3 | 1 | 0 | 12 | 12: 4 = 3 |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | F-1 | |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | F-1 | |
| 0 | 1 | -1/4 | 1/4 | 0 | 4 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| 0 | 0 | 7/4 | 1/4 | 1 | 6 | |
| 0 | 0 | -2 | -1 | 0 | F-13 |
| S1 = 0 S2 = 0 x 1 = 3 x 2 = 4 S 3 = 6 |
=> F - 13 = 0 => F = 13 |
Servisni zadatak. Servis je namijenjen za online rješavanje problema linearnog programiranja (LPP) korištenjem simpleks metode u sljedećim notacijskim oblicima:
- u obliku simpleks tabele (metoda Jordanovih transformacija); osnovni oblik zapisa;
- modifikovana simpleks metoda; u obliku kolone; u linijskom obliku.
Uputstvo. Odaberite broj varijabli i broj redova (broj ograničenja). Rezultirajuće rješenje se pohranjuje u Word i Excel datoteku.
U ovom slučaju ne uzimajte u obzir ograničenja tipa x i ≥ 0. Ako nema ograničenja u zadatku za neki x i, onda se LLP mora svesti na KZLP, ili koristiti ovu uslugu. Rješenje automatski određuje upotrebu M-metoda(jednostavna metoda sa umjetnom osnovom) i dvostepena simpleks metoda.Sa ovim kalkulatorom se također koriste sljedeće:
Grafička metoda za rješavanje LLP
Rješenje transportnog problema
Rešenje matrične igre
Koristeći online uslugu, možete odrediti cijenu matrične igre (donje i gornje granice), provjeriti sedlo, pronaći rješenje za mješovitu strategiju koristeći sljedeće metode: minimaks, simpleks metoda, grafička (geometrijska) metoda, Brownova metoda.
Ekstremum funkcije dvije varijable
Problemi sa dinamičkim programiranjem
Rasporediti 5 homogenih serija robe na tri tržišta na način da ostvarite maksimalan prihod od njihove prodaje. Prihod od prodaje na svakom tržištu G(X) zavisi od broja prodatih serija robe X i prikazan je u tabeli.
| Volumen 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 |
Simpleks metodski algoritam uključuje sljedeće korake:
- Izrada prvog osnovnog plana. Prelazak na kanonski oblik problema linearnog programiranja uvođenjem nenegativnih dodatnih varijabli bilansa.
- Provjera optimalnosti plana. Ako postoji barem jedan koeficijent reda indeksa manji od nule, tada plan nije optimalan i treba ga poboljšati.
- Definiranje vodećih kolona i redova. Od negativnih koeficijenata indeksne linije bira se najveći u apsolutnoj vrijednosti. Zatim dijeli elemente stupca slobodnih članova simpleks tablice na elemente istog predznaka vodeće kolone.
- Izgradnja nove osnove. Prijelaz na novi plan vrši se kao rezultat ponovnog izračunavanja simpleks tablice Jordan-Gaussovom metodom.
Ako je potrebno pronaći ekstremum funkcije cilja, onda je riječ o pronalaženju minimalne vrijednosti (F(x) → min , vidi primjer rješavanja minimizacije funkcije) i maksimalne vrijednosti ((F(x) ) → max , vidi primjer rješavanja maksimizacije funkcije)
Ekstremno rješenje se postiže na granici područja izvodljivih rješenja u jednom od vrhova uglovnih tačaka poligona, ili na segmentu između dvije susjedne kutne tačke.
Osnovna teorema linearnog programiranja. Ako funkcija cilja LLP dostigne ekstremnu vrijednost u nekoj tački u području izvodljivih rješenja, tada preuzima ovu vrijednost u kutnoj tački. Ako funkcija cilja LLP dostigne ekstremnu vrijednost u više od jedne kutne točke, tada poprima istu vrijednost u bilo kojoj od konveksnih linearnih kombinacija ovih tačaka.
Suština simpleks metode. Kretanje do optimalne tačke se vrši pomeranjem od jedne ugaone tačke do sledeće, što približava i brže X opt. Takva šema nabrajanja bodova, nazvana simpleks metoda, predložio R. Danzig.
Ugaone tačke karakteriše m osnovnih varijabli, pa se prelazak sa jedne ugaone tačke na susednu može izvršiti promenom samo jedne osnovne varijable u bazi u promenljivu iz nebazne.
Implementacija simpleks metode, zbog različitih karakteristika i formulacija LP problema, ima različite modifikacije.
Konstrukcija simpleks tablica se nastavlja sve dok se ne dobije optimalno rješenje. Kako koristiti simpleks tablicu da odredimo da je rješenje problema linearnog programiranja optimalno?
Ako posljednji red (vrijednosti objektivne funkcije) ne sadrži negativne elemente, tada će pronaći optimalni plan.
Napomena 1. Ako je jedna od osnovnih varijabli jednaka nuli, tada je ekstremna tačka koja odgovara takvom osnovnom rješenju degenerirana. Degeneracija se javlja kada postoji nejasnoća u izboru vodećeg reda. Možda uopće nećete primijetiti degeneraciju problema ako odaberete drugu liniju kao vodič. U slučaju nejasnoće, red sa najnižim indeksom treba odabrati kako bi se izbjeglo ponavljanje.
Napomena 2. Neka su u nekoj ekstremnoj tački sve simpleks razlike nenegativne D k ³ 0 (k = 1..n+m), tj. dobijeno je optimalno rješenje i postoji takav A k - nebazični vektor, za koji je D k = 0. Tada se maksimum postiže najmanje u dvije tačke, tj. postoji alternativni optimum. Ako ovu varijablu x k uvedemo u bazu, vrijednost ciljne funkcije se neće promijeniti.
Napomena 3. Rješenje dualnog problema je u posljednjoj simpleks tabeli. Posljednjih m komponenti vektora simpleksnih razlika (u stupcima balansnih varijabli) su optimalno rješenje dualnog problema. Vrijednosti ciljnih funkcija direktnog i dualnog problema u optimalnim tačkama su iste.
Napomena 4. Prilikom rješavanja problema minimizacije u bazu se uvodi vektor sa najvećom pozitivnom simpleks razlikom. Nadalje, primjenjuje se isti algoritam kao i za problem maksimizacije.
Ako je postavljen uslov "Potrebno je da se sirovine tipa III potpuno utroše", onda je odgovarajući uslov jednakost.
Problemi linearnog programiranja. Ona je u sekvencijalnoj konstrukciji koja karakteriše proces koji se razmatra. Rješenje je podijeljeno u tri glavne faze: izbor varijabli, konstrukcija sistema ograničenja i potraga za ciljnom funkcijom.
Na osnovu ove podjele, uvjet problema se može preformulisati na sljedeći način: ekstremum ciljne funkcije Z(X) = f(x1, x2, … ,xn) → max (min) i odgovarajuće varijable, ako je poznato da zadovoljavaju sistem ograničenja: Φ_i ( x1, x2, … ,xn) = 0 za i = 1, 2, …, k; Φ_i (x1, x2, … ,xn)) 0 za i = k+1 , k+2, …, m.
Sistem ograničenja se mora svesti na kanonski oblik, tj. na sistem linearnih jednačina, gdje je broj varijabli veći od broja jednačina (m > k). U ovom sistemu sigurno će postojati varijable koje se mogu izraziti drugim varijablama, a ako to nije slučaj, onda se one mogu uvesti umjetno. U ovom slučaju, prvi se nazivaju osnova ili umjetna osnova, a drugi se nazivaju slobodnim.
Pogodnije je razmotriti simpleks metodu na konkretnom primjeru. Neka je zadana linearna funkcija f(x) = 6x1 + 5x2 + 9x3 i sistem ograničenja: 5x1 + 2x2 + 3x3 ≤ 25, x1 + 6x2 + 2x3 ≤ 20, 4x1 + 3x3 ≤ 18. Potrebno je da se pronađe. maksimalna vrijednost funkcije f(x).
Rješenje U prvoj fazi zadajte početno (referentno) rješenje sistema jednačina na apsolutno proizvoljan način, koje mora zadovoljiti dati sistem ograničenja. U ovom slučaju je potrebno uvođenje vještačkog, tj. bazne varijable x4, x5 i x6 kako slijedi: 5x1 + 2x2 + 3x3 + x4 = 25; x1 + 6x2 + 2x3 + x5 = 20; 4x1 + 3x3 + x6 = 18.
Kao što vidite, nejednakosti su transformisane u jednakosti zahvaljujući dodanim varijablama x4, x5, x6, koje nisu negativne vrijednosti. Dakle, doveli ste sistem u kanonski oblik. Promenljiva x4 ulazi u prvu jednačinu sa koeficijentom 1, au dve - sa koeficijentom 0, isto važi i za varijable x5, x6 i odgovarajuće jednačine, što odgovara definiciji baze.
Pripremili ste sistem i pronašli početno referentno rješenje - X0 = (0, 0, 0, 25, 20, 18). Sada predstavite koeficijente varijabli i konstantne članove jednadžbi (brojeve desno od znaka “=”) u obliku tabele da biste optimizovali dalje proračune (vidi sliku).
Suština simpleks metode je da se ova tabela dovede u formu u kojoj će sve cifre u nizu L biti nenegativne vrijednosti. Ako se pokaže da je to nemoguće, onda sistem uopće nema optimalno rješenje. Prvo odaberite najmanji element ove linije, a to je -9. Broj je u trećoj koloni. Pretvorite odgovarajuću varijablu x3 u osnovnu varijablu. Da biste to učinili, podijelite niz sa 3 da biste dobili 1 u ćeliji.
Sada su vam potrebne ćelije i okrenite na 0. Da biste to učinili, oduzmite od odgovarajućih brojeva trećeg reda za 3. Od elemenata drugog reda - elemente trećeg, pomnožene sa 2. I, konačno, od elementi linije L - pomnoženi sa (-9). Dobili ste drugo pivot rješenje: f(x) = L = 54 za x1 = (0, 0, 6, 7, 8, 0).
