U grafičkoj metodi rješavanja problema LP zapravo smo iz skupa vrhova koji pripadaju granici skupa rješenja sustava nejednadžbi odabrali vrh na kojem je vrijednost ciljne funkcije dosegla maksimum (minimum). U slučaju dvije varijable, ova metoda je potpuno intuitivna i omogućuje vam brzo pronalaženje rješenja problema.
Ako problem ima tri ili više varijabli, au stvarnim ekonomskim problemima je upravo takva situacija, teško je vizualizirati područje rješenja sustava ograničenja. Takvi se problemi rješavaju pomoću simpleks metoda ili metodom sukcesivnih 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 je li plan optimalan. Ako da, onda je problem riješen. Ako ne, onda idemo na drugi poboljšani plan - na drugi vrh. vrijednost funkcije cilja na ovoj ravnini (na ovom vrhu) je očito bolja nego u prethodnoj. Algoritam prijelaza provodi se pomoću određenog računskog koraka, koji je prikladno zapisan u obliku tablica tzv. simpleks tablice . Kako postoji konačan broj vrhova, u konačnom broju koraka dolazimo do optimalnog rješenja.
Razmotrimo simpleks metodu na konkretnom primjeru problema izrade plana.
Napomenimo još jednom da je simpleks metoda primjenjiva za rješavanje kanonskih LP problema svedenih na poseban oblik, tj. koji imaju bazu, pozitivne desne strane i ciljnu funkciju izraženu kroz nebazične varijable. Ako zadatak nije sveden na poseban oblik, tada su potrebni dodatni koraci, o kojima ćemo kasnije govoriti.
Razmotrimo problem proizvodnog plana, nakon što smo prethodno konstruirali model i doveli ga u poseban oblik.
Zadatak.
Za proizvodnju proizvoda A I U Skladište može osloboditi više od 80 jedinica sirovina. Štoviše, za proizvodnju proizvoda A troše se dvije jedinice, a proizvodi U- jedna jedinica sirovina. Proizvodnju je potrebno planirati tako da se osigura najveći profit ako proizvodi A potrebno je proizvesti najviše 50 komada, a proizvoda U- ne više od 40 kom. Štoviše, dobit od prodaje jednog proizvoda A- 5 rubalja, i od U- 3 trljati.
Izgradimo matematički model, označavajući x 1 količina proizvoda A u planu, za x 2 - broj proizvoda U. tada će sustav ograničenja izgledati ovako:
Dovedimo problem u kanonski oblik uvođenjem dodatnih varijabli:
(3.10)
F = -5x 1 - 3x 2 → min.
Ovaj problem ima poseban oblik (s bazom, desne strane su nenegativne). Može se riješiti simpleks metodom.
japozornici. Zapisivanje problema u simpleks tablicu. Postoji korespondencija jedan na jedan između sustava ograničenja problema (3.10) i simpleks tablice. U tablici ima onoliko redaka koliko ima jednakosti u sustavu ograničenja, a ima onoliko stupaca koliko ima slobodnih varijabli. Osnovne varijable ispunjavaju prvi stupac, slobodne varijable ispunjavaju gornji red tablice. Donja crta naziva se indeksna linija iu njoj su zapisani koeficijenti varijabli u funkciji cilja. U donjem desnom kutu početno se ispisuje 0 ako u funkciji nema slobodnog člana; ako postoji, onda ga napišite sa suprotnim predznakom. Na ovom mjestu (u donjem desnom kutu) nalazit će se vrijednost funkcije cilja, koja bi trebala porasti u apsolutnoj vrijednosti pri prelasku iz jedne tablice u drugu. Dakle, tablica 3.4 odgovara našem sustavu ograničenja, te možemo prijeći na fazu II rješenja.
Tablica 3.4
|
Osnovni, temeljni |
besplatno |
||
IIpozornici. Provjera optimalnosti referentnog plana.
Ova tablica 3.4 odgovara sljedećem referentnom planu:
(x 1 , x 2 , x 3 , x 4 , x 5) = (0, 0, 50, 40, 80).
Slobodne varijable x 1 , x 2 jednako 0; x 1 = 0, x 2 = 0. I osnovne varijable x 3 , x 4 , x 5 uzeti vrijednosti x 3 = 50, x 4 = 40, x 5 = 80 - iz stupca slobodnih termina. Vrijednost ciljne funkcije:
-F = - 5x 1 - 3x 2 = -5 0 - 3 0 = 0.
Naš zadatak je provjeriti je li zadani referentni plan optimalan. Da biste to učinili, morate pogledati liniju indeksa - liniju ciljne funkcije F.
Moguće su razne situacije.
1. U kazalu F- u nizu nema negativnih elemenata. To znači da je plan optimalan i da se može zapisati rješenje problema. Funkcija cilja je dosegla svoju optimalnu vrijednost, jednaku broju u donjem desnom kutu, uzetom sa suprotnim predznakom. Prijeđimo na fazu IV.
2. Indeksni red ima najmanje jedan negativan element čiji stupac nema pozitivnih elemenata. Tada zaključujemo da funkcija cilja F→∞ opada bez ograničenja.
3. Indeksni red ima negativan element koji ima barem jedan pozitivan element u svom stupcu. Zatim prelazimo na sljedeću fazu III. Ponovno izračunavamo tablicu, poboljšavajući referentni plan.
IIIpozornici. Poboljšanje referentnog plana.
Od negativnih elemenata indeksa F-redova odaberite onaj s najvećim modulom, pozovite razrješavanje odgovarajućeg stupca i označite ga s “”.
Za odabir razrješujućeg retka potrebno je izračunati omjere elemenata stupca slobodnih pojmova samo Do pozitivan elementi stupca rezolucije. Od dobivenih relacija odaberite minimalnu. Odgovarajući element kod kojeg je postignut minimum naziva se razrješenje. Istaknut ćemo ga kvadratom.
U našem primjeru, 
, element 2 je permisivan. Pravac koji odgovara ovom elementu naziva se i razrješavanje (tablica 3.5).
Tablica 3.5
Odabirom dopuštenog elementa, ponovno izračunavamo tablicu prema pravilima:
1. U novoj tablici iste veličine kao i prije, varijable retka i stupca razrješenja su zamijenjene, što odgovara prijelazu na novu bazu. U našem primjeru: x 1 je umjesto toga uključen u osnovu x 5, koji napušta bazu i sada je slobodan (tablica 3.6).
Tablica 3.6
|
Osnovni, temeljni |
besplatno |
||
2. Umjesto razlučnog elementa 2 upiši njegov inverzni broj.
3. Elemente rezolucijske linije dijelimo s elementom rezolucije.
4. Elemente stupca razlučivosti podijelimo s elementom razlučivosti i zapišemo sa suprotnim predznakom.
5. Da bismo ispunili preostale elemente tablice 3.6, ponovno izračunavamo pomoću pravila pravokutnika. Recimo da želimo prebrojati element na poziciji 50.
Mentalno povezujemo ovaj element s razrješavajućim, pronalazimo proizvod, oduzimamo proizvod elemenata koji se nalaze na drugoj dijagonali rezultirajućeg pravokutnika. Razliku dijelimo s elementom razrješenja.
Dakle, . Pišemo 10 na mjestu gdje je bilo 50. Slično :
, 
, , 
.
Tablica 3.7
Imamo novu tablicu 3.7, osnovne varijable su sada varijable (x 3,x 4,x 1). Vrijednost funkcije cilja postala je jednaka -200, tj. smanjila se. Da bismo provjerili optimalnost ovog osnovnog rješenja, moramo ponovno prijeći na stupanj II. Proces je očito konačan; kriterij zaustavljanja su točke 1 i 2 faze II.
Dovršimo rješenje zadatka. Da bismo to učinili, provjerimo redak indeksa i, vidjevši u njemu negativan element, pozovimo rješavanje odgovarajućeg stupca i, prema stupnju III, ponovno izračunajmo tablicu. Nakon što smo sastavili relacije i među njima odabrali minimalnu = 40, odredili smo razlučni element 1. Sada provodimo preračun prema pravilima 2-5.
Tablica 3.8
|
Osnovni, temeljni |
besplatno |
||
|
x 3 = 30, x 2 = 40, x 1 = 20. Slobodne varijable su 0, x 5 = 0, x 4 = 0. Funkcija cilja uzima vrijednost zadnjeg elementa stupca slobodnih članova sa suprotnim predznakom: - F = -220 F = 220, u našem primjeru funkcija je ispitana na min, a početno F max, tako da se znak zapravo dvaput promijenio. Tako, x* = (20, 40, 30, 0, 0), F* = 220. Odgovor na zadatak: U plan proizvodnje potrebno je uvrstiti 20 proizvoda te vrste A, 40 proizvoda tipa B, dok će dobit biti maksimalna i bit će jednaka 220 rubalja. Na kraju ovog odjeljka predstavljamo dijagram toka algoritma metode simplex, koji točno ponavlja korake, ali možda će nekim čitateljima biti prikladniji za korištenje, budući da strelice pokazuju jasan smjer radnji. Veze iznad okvira u dijagramu toka pokazuju kojoj fazi ili podtočki pripada odgovarajuća grupa transformacija. pravilo za pronalaženje početnog referentnog plana bit će formulirano u stavku 3.7.
Pitanja za samokontrolu 1. Kako se konstruira simpleks tablica? 2. Kako se promjena osnovice odražava u tablici? 3. Formulirajte kriterij zaustavljanja za simpleks metodu. 4. Kako organizirati preračunavanje tablice? 5. Iz kojeg retka je zgodno započeti preračunavanje tablice? |
. Algoritam Simplex metode
Primjer 5.1. Simpleks metodom riješite sljedeći problem linearnog programiranja:
Riješenje:
ja ponavljanje:
x3, x4, x5, x6 x1,x2. Izrazimo osnovne varijable u terminima slobodnih:
Svedimo funkciju cilja na sljedeći oblik:
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 (slobodni broj ove crte se ne uzima u obzir pri razmatranju ovog kriterija). 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 evaluacijskom omjeru prihvaća se 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 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 rezolucije tablice 5.4 s elementom rezolucije ove simpleks tablice, a rezultat se uzima sa suprotnim predznakom. 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 dobivena je nova simpleks 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.
Pronađeno osnovno rješenje je prihvatljivo, određujemo stupce 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.
Pronađeno osnovno rješenje je prihvatljivo, određujemo stupce 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 simpleks transformacija dobiveno je novo osnovno rješenje, a 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.
Pronađeno rješenje je jedinstveno, jer nema nulti elemenata u liniji funkcije cilja (tablica 5.9) (slobodni broj ove crte se ne uzima u obzir pri razmatranju ove karakteristike).
Odgovor: optimalna vrijednost funkcije cilja razmatranog problema =24, koja se postiže pri.
Primjer 5.2. Riješite gornji problem linearnog programiranja pod uvjetom da je funkcija cilja minimizirana:
Riješenje:
ja ponavljanje:
Faza 1: formiranje početne simpleks tablice.
Izvorni problem linearnog programiranja dan je u standardnom obliku. Dovedimo ga u kanonski oblik uvođenjem dodatne ne-negativne varijable u svako od ograničenja nejednakosti, 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.
| - | x 1 | + | x 2 | - | S 1 | = | 1 | ||||||||||
| x 1 | +3 | x 2 | + | S 2 | = | 15 | |||||||||||
| - | 2 | x 1 | + | x 2 | + | S 3 | = | 4 |
| - | x 1 | + | x 2 | - | S 1 | + | R 1 | = | 1 | |||||||||||
| x 1 | +3 | x 2 | + | S 2 | = | 15 | ||||||||||||||
| - | 2 | x 1 | + | x 2 | + | S 3 | = | 4 |
| x 1 = 0 x 2 = 0 S 1 = 0 S 2 = 15 S 3 = 4 R 1 = 1 |
=> W = 1 |
| x 1 | x 2 | S 1 | S 2 | S 3 | R 1 | 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 | W - 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 | W - 0 |
| - | x 1 | + | x 2 | - | S 1 | = | 1 | ||||||||||
| 4 | x 1 | + | 3 | S 1 | + | S 2 | = | 12 | |||||||||
| - | x 1 | + | S 1 | + | S 3 | = | 3 |
| x 1 | x 2 | S 1 | S 2 | S 3 | 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 |
| S 1 = 0 S 2 = 0 x 1 = 3 x 2 = 4 S 3 = 6 |
=> F - 13 = 0 => F = 13 |
Svrha usluge. Usluga je dizajnirana za online rješavanje problema linearnog programiranja (LPP) koristeći simpleks metodu u sljedećim notnim oblicima:
- u obliku simpleks tablice (metoda Jordanove transformacije); osnovni obrazac za snimanje;
- modificirana simpleks metoda; u obliku stupca; u linijskom obliku.
upute. Odaberite broj varijabli i broj redaka (broj ograničenja). Dobiveno rješenje sprema se u Word i Excel datoteku.
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 igre matrice
Pomoću internetske usluge možete odrediti cijenu matrične igre (donje i gornje granice), provjeriti prisutnost sedlaste točke, pronaći rješenje za mješovitu strategiju pomoću sljedećih metoda: minimaks, simpleks metoda, grafička (geometrijska ) metoda, Brownova metoda.
Ekstrem funkcije dviju varijabli
Problemi dinamičkog programiranja
Podijelite 5 homogenih serija robe između tri tržišta kako biste ostvarili najveći prihod od njihove prodaje. Prihod od prodaje na svakom tržištu G(X) ovisi o broju prodanih serija proizvoda X i prikazan je u tablici.
| Količina proizvoda X (u serijama) | Prihod G(X) | ||
| 1 | 2 | 3 | |
| 0 | 0 | 0 | 0 |
| 1 | 28 | 30 | 32 |
| 2 | 41 | 42 | 45 |
| 3 | 50 | 55 | 48 |
| 4 | 62 | 64 | 60 |
| 5 | 76 | 76 | 72 |
Algoritam Simplex metode uključuje sljedeće korake:
- Izrada prvog temeljnog plana. Prijelaz na kanonski oblik problema linearnog programiranja uvođenjem nenegativnih dodatnih bilančnih varijabli.
- Provjera optimalnosti plana. Ako postoji barem jedan koeficijent indeksne linije manji od nule, tada plan nije optimalan i potrebno ga je poboljšati.
- Određivanje vodećeg stupca i retka. Od negativnih koeficijenata indeksne linije odabire se najveći u apsolutnoj vrijednosti. Zatim se elementi stupca slobodnih članova simpleks tablice dijele na elemente istog predznaka vodećeg stupca.
- Izrada novog referentnog plana. Prijelaz na novi plan provodi se kao rezultat ponovnog izračuna simpleksne tablice metodom Jordan-Gauss.
Ako je potrebno pronaći ekstrem funkcije cilja, tada govorimo o pronalaženju minimalne vrijednosti (F(x) → min, vidi primjer rješenja minimiziranja funkcije) i maksimalne vrijednosti ((F(x ) → max, pogledajte primjer rješenja za maksimiziranje funkcije)
Ekstremno rješenje postiže se na granici područja mogućih rješenja na jednom od vrhova kutnih točaka poligona ili na segmentu između dvije susjedne kutne točke.
Temeljni teorem linearnog programiranja. Ako funkcija cilja ZLP dosegne ekstremnu vrijednost u nekoj točki u području mogućih rješenja, tada preuzima tu vrijednost u kutnoj točki. Ako funkcija cilja ZLP dosegne ekstremnu vrijednost u više od jedne kutne točke, tada uzima istu vrijednost u bilo kojoj od konveksnih linearnih kombinacija tih točaka.
Suština simpleks metode. Kretanje do optimalne točke provodi se pomicanjem od jedne kutne točke do susjedne, čime se približava i brže X opt. Takva shema za nabrajanje točaka, nazvana simpleks metoda, predložio R. Danzig.
Kutne točke karakteriziraju m osnovnih varijabli, pa se prijelaz iz jedne kutne točke u susjednu može ostvariti promjenom samo jedne osnovne varijable u bazi u varijablu iz nebaze.
Implementacija simpleks metode, zbog različitih karakteristika i formulacija problema LP, ima različite modifikacije.
Izrada simpleks tablica nastavlja se sve dok se ne dobije optimalno rješenje. Kako možete koristiti simpleks tablicu da odredite da je rješenje problema linearnog programiranja optimalno?
Ako zadnji redak (vrijednosti funkcije cilja) ne sadrži negativne elemente, dakle, pronaći će optimalni plan.
Napomena 1. Ako je jedna od osnovnih varijabli jednaka nuli, tada je ekstremna točka koja odgovara takvom osnovnom rješenju degenerirana. Degeneracija se javlja kada postoji dvosmislenost u izboru linije vodilje. Možda uopće nećete primijetiti degeneraciju problema ako odaberete drugu liniju kao vodič. U slučaju dvosmislenosti treba odabrati redak s najnižim indeksom kako bi se izbjeglo ponavljanje.
Napomena 2. Neka su u nekoj ekstremnoj točki sve simpleksne razlike nenegativne D k ³ 0 (k = 1..n+m), tj. dobije se optimalno rješenje i postoji A k - vektor bez baze za koji je D k = 0. Tada se maksimum postiže barem u dvije točke, t.j. 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.
Problemi linearnog programiranja. Nalazi se u sekvencijalnoj konstrukciji koja karakterizira proces koji se razmatra. Rješenje je podijeljeno u tri glavne faze: izbor varijabli, konstrukcija sustava ograničenja i traženje funkcije cilja.
Na temelju ove podjele, uvjet problema može se preformulirati na sljedeći način: ekstrem funkcije cilja Z(X) = f(x1, x2, … ,xn) → max (min) i odgovarajuće varijable, ako je poznato da one zadovoljavaju sustav ograničenja: Φ_i ( x1, x2, … ,xn) = 0 za i = 1, 2, …, k; Φ_i (x1, x2, … ,xn)) 0 za i = k+1, k+ 2, …, m.
Sustav ograničenja mora se dovesti u kanonski oblik, tj. sustavu linearnih jednadžbi, gdje je broj varijabli veći od broja jednadžbi (m > k). U ovom sustavu sigurno će postojati varijable koje se mogu izraziti kroz druge varijable, a ako to nije slučaj, onda se one mogu unijeti umjetno. U tom se slučaju prvi nazivaju osnova ili umjetna osnova, a drugi se nazivaju slobodni.
Pogodnije je razmotriti simpleks metodu koristeći određeni primjer. Neka je zadana linearna funkcija f(x) = 6x1 + 5x2 + 9x3 i sustav ograničenja: 5x1 + 2x2 + 3x3 ≤ 25; x1 + 6x2 + 2x3 ≤ 20; 4x1 + 3x3 ≤ 18. Moramo pronaći maksimum vrijednost funkcije f(x).
Rješenje U prvoj fazi zadajte početno (referentno) rješenje sustava jednadžbi na apsolutno proizvoljan način, koje mora zadovoljiti zadani sustav ograničenja. U ovom slučaju potrebno je uvođenje umjetnog, tj. osnovne varijable x4, x5 i x6 kako slijedi: 5x1 + 2x2 + 3x3 + x4 = 25; x1 + 6x2 + 2x3 + x5 = 20; 4x1 + 3x3 + x6 = 18.
Kao što vidite, nejednadžbe su pretvorene u jednakosti zahvaljujući dodanim varijablama x4, x5, x6, koje su nenegativne veličine. Time ste doveli sustav u njegovu kanonsku formu. Varijabla x4 je uključena u prvu jednadžbu s koeficijentom 1, au drugu jednadžbu s koeficijentom 0, isto vrijedi i za varijable x5, x6 i pripadajuće jednadžbe, što odgovara definiciji baze.
Pripremili ste sustav i pronašli početno referentno rješenje – X0 = (0, 0, 0, 25, 20, 18). Sada predstavite koeficijente varijabli i slobodne članove jednadžbi (brojeve desno od znaka “=”) u obliku tablice kako biste optimizirali daljnje izračune (vidi sliku).
Bit simpleks metode je dovesti ovu tablicu u oblik u kojem će svi brojevi u retku L biti nenegativne vrijednosti. Ako se pokaže da je to nemoguće, onda sustav uopće nema optimalno rješenje. Prvo odaberite najmanji element ove linije, a to je -9. Broj je u trećem stupcu. Pretvorite odgovarajuću x3 varijablu u baznu varijablu. Da biste to učinili, liniju podijelite s 3 tako da ćelija završi s 1.
Sada trebate ćelije i okrenuti se na 0. Da biste to učinili, oduzmite od odgovarajućih brojeva trećeg retka za 3. Od elemenata drugog retka - elemente trećeg, pomnoženo s 2. I, konačno, od elementi reda L - pomnoženi s (-9). Dobili ste drugo referentno rješenje: f(x) = L = 54 s x1 = (0, 0, 6, 7, 8, 0).
