Ovdje je ručno (ne aplet) rješenje dvaju problema koristeći simplex metodu (slično rješenju s apletom) s detaljna objašnjenja kako bi razumjeli algoritam rješavanja problema simpleks metodom. Prvi zadatak sadrži znakove nejednakosti samo “≤” (problem s početnom bazom), drugi može sadržavati znakove “≥”, “≤” ili “=” (problem s umjetnom bazom), različito se rješavaju.

Simpleksna metoda, rješavanje problema s početnom bazom

1)Simpleks metoda za problem s početnom bazom (svi znakovi nejednakosti ograničenja " ≤ ").

Upišimo problem kanonski obliku, tj. prepisujemo ograničenja nejednakosti u obliku jednakosti, dodajući bilanca stanja varijable:

Ovaj sustav je sustav s bazom (baze s 1, s 2, s 3, svaka od njih je uključena u samo jednu jednadžbu sustava s koeficijentom 1), x 1 i x 2 su slobodne varijable. Problemi koji se rješavaju simpleks metodom moraju imati sljedeća dva svojstva: - sustav ograničenja mora biti sustav jednadžbi s bazom; -slobodni članovi svih jednadžbi u sustavu moraju biti nenegativni.

Rezultirajući sustav je sustav s bazom i njegovi slobodni članovi su nenegativni, tako da se možemo primijeniti simpleks metoda. Kreirajmo prvu simpleks tablicu (Iteracija 0) za rješavanje problema simpleks metoda, tj. tablicu koeficijenata funkcije cilja i sustav jednadžbi za pripadajuće varijable. Ovdje "BP" znači stupac osnovnih varijabli, "Rješenje" znači stupac desnih strana jednadžbi sustava. Rješenje nije optimalno, jer postoje negativni koeficijenti u z-retku.

iteracija simpleks metode 0

Kako bismo poboljšali rješenje, prijeđimo na sljedeću iteraciju simpleks metoda, dobivamo sljedeću simpleks tablicu. Da biste to učinili, morate odabrati omogućiti stupac, tj. varijabla koja će biti uključena u bazu pri sljedećoj iteraciji simpleks metode. Odabire se prema najvećem apsolutnom negativnom koeficijentu u z-retku (u problemu maksimuma) - u početnoj iteraciji simpleks metode to je stupac x 2 (koeficijent -6).

Zatim odaberite omogućiti niz, tj. varijablu koja će napustiti bazu pri sljedećoj iteraciji simpleks metode. Odabire se najmanjim omjerom stupca “Odluka” prema odgovarajućim pozitivnim elementima stupca rezolucije (stupac “Omjer”) - u početnoj iteraciji to je red s 3 (koeficijent 20).

Permisivni element nalazi se na sjecištu razlučujućeg stupca i razlučujućeg retka, njegova ćelija je označena bojom, jednaka je 1. Stoga će pri sljedećoj iteraciji simpleks metode varijabla x 2 zamijeniti s 1 u bazi. Imajte na umu da se odnos ne traži u z-stringu; tamo se stavlja crtica "-". Ako postoje identični minimalni odnosi, odabire se bilo koji od njih. Ako su svi koeficijenti u stupcu rezolucije manji ili jednaki 0, tada je rješenje problema beskonačno.

Ispunimo sljedeću tablicu “Iteracija 1”. Dobit ćemo ga iz tablice “Iteration 0”. Cilj daljnjih transformacija je pretvoriti stupac rezolucije x2 u stupac jedinice (s jedinicom umjesto elementa rezolucije i nulama umjesto preostalih elemenata).

1) Izračunajte redak x 2 tablice "Iteracija 1". Prvo, podijelimo sve članove razrješavajućeg retka s 3 tablice "Iteracija 0" s razlučujućim elementom (u ovom slučaju je jednak 1) ove tablice, dobivamo redak x 2 u tablici "Iteracija 1" . Jer razlučujući element u ovom slučaju jednak je 1, tada će se red s 3 tablice "Iteracija 0" podudarati s retkom x 2 tablice "Iteracija 1". Red x 2 tablice Iteracije 1 dobili smo 0 1 0 0 1 20, preostali redovi tablice Iteracije 1 bit će dobiveni iz ovog retka i redaka tablice Iteracije 0 kako slijedi:

2) Izračun z-retka tablice "Iteracija 1". Umjesto -6 u prvom retku (z-redak) u stupcu x2 tablice Iteracije 0, treba postojati 0 u prvom retku tablice Iteracije 1. Da biste to učinili, pomnožite sve elemente retka x 2 tablice "Iteracija 1" 0 1 0 0 1 20 sa 6, dobit ćemo 0 6 0 0 6 120 i zbrojite ovaj red s prvim redom (z - red) tablice "Iteracija 0" -4 -6 0 0 0 0, dobivamo -4 0 0 0 6 120. U stupcu x 2 pojavljuje se nula 0, cilj je postignut. Elementi stupca rezolucije x 2 označeni su crvenom bojom.

3) Izračun retka s 1 tablice "Iteracija 1". Umjesto 1 u prvom retku tablice "Iteracija 0" trebala bi stajati 0 u tablici "Iteracija 1". Da biste to učinili, pomnožite sve elemente retka x 2 tablice "Iteracija 1" 0 1 0 0 1 20 s -1, dobijete 0 -1 0 0 -1 -20 i dodajte ovaj red sa s 1 - redom tablici "Iteration 0" 2 1 1 0 0 64, dobivamo redak 2 0 1 0 -1 44. U stupcu x 2 dobivamo traženu 0.

4) Izračunajte red s 2 u tablici "Iteracija 1". Na mjestu 3 u s 2 retku tablice "Iteracija 0" treba biti 0 u tablici "Iteracija 1". Da biste to učinili, pomnožite sve elemente retka x 2 tablice “Iteracija 1” 0 1 0 0 1 20 s -3, dobijete 0 -3 0 0 -3 -60 i dodajte ovaj red sa s 1 - retkom tablice “Iteracija 0” 1 3 0 1 0 72, dobivamo redak 1 0 0 1 -3 12. U stupcu x 2 dobivena je tražena 0. Stupac x 2 u tablici “Iteracija 1” postao je jedinica , sadrži jednu 1, a ostatak 0.

Redovi tablice "Iteracija 1" dobivaju se prema sljedećem pravilu:

Novi red = Stari red – (Koeficijent stupca rezolucije starog retka)*(Novi redak rezolucije).

Na primjer, za z-string imamo:

Stari z-niz (-4 -6 0 0 0 0) -(-6)*Novi razrješavajući niz -(0 -6 0 0 -6 -120) =Novi z-niz (-4 0 0 0 6 120).

Za sljedeće tablice preračunavanje elemenata tablice radi se na sličan način, pa ga izostavljamo.

iteracija simpleks metode 1

Razrješavanje stupca x 1, razrješavanje reda s 2, s 2 izlazi iz baze, x 1 ulazi u bazu. Na potpuno isti način dobivamo preostale simpleks tablice dok ne dobijemo tablicu sa svim pozitivnim koeficijentima u z-retku. Ovo je znak optimalne tablice.

iteracija simpleks metode 2

Razrješavajući stupac s 3, razrješavajući red s 1, s 1 izlazi iz baze, s 3 ulazi u bazu.

iteracija simpleks metode 3

U z-retku svi koeficijenti su nenegativni, pa je dobiveno optimalno rješenje x 1 = 24, x 2 = 16, z max = 192.

Da biste omogućili pokretanje appleta na vašem računalu, morate učiniti sljedeće - kliknite Start>Upravljačka ploča>Programi>Java. U prozoru Java Control Panel odaberite karticu Security, kliknite gumb Edit Site List, gumb add i zalijepite put do ove stranice iz adresne trake preglednika u slobodno polje. Zatim kliknite OK, a zatim ponovno pokrenite računalo.

Za pokretanje appleta kliknite na gumb "Simplex". Ako gumb "Simplex" nije vidljiv iznad ove linije, tada Java nije instalirana na vašem računalu.

Nakon klika na gumb “Simplex” pojavljuje se prvi prozor za unos broja varijabli i broja ograničenja zadatka na simplex metodi.

Nakon klika na gumb “ok” pojavljuje se prozor za unos preostalih podataka zadatka simplex metode: način prikaza ( decimale ili obični), tip zadatka kriterij min ili max, unos koeficijenata funkcije cilja i koeficijenata sustava ograničenja s predznacima “≤”, “≥” ili “=”, ograničenja oblika x i ≥ 0 ne potrebno je unijeti, uzima ih u obzir u svom algoritmu.

Nakon klika na gumb “Riješi” pojavljuje se prozor s rezultatima rješavanja problema .Prozor se sastoji od dva dijela; u gornjem dijelu nalazi se tekstualno polje s opisom redukcije izvornog problema kanonski oblik, koji se koristi za sastavljanje prve simpleks tablice. Na dnu prozora, u ploči s karticama, nalaze se simpleks tablice svake iteracije s malim tekstualnim poljem na dnu koje označava stupac razlučivosti, red razlučivosti i druge informacije, što čini program treningom. U kartici s optimalnom (zadnjom) tablicom u tekstualnom polju prikazano je rezultirajuće optimalno rješenje problema.

Pošaljite sve pogreške koje primijetite i komentare na aplet na: [e-mail zaštićen] ili nazovite 8 962 700 77 06, na čemu ćemo vam biti jako zahvalni.

Program M-metode

Program za rješavanje transportnog problema

Ovdje je ručno (ne applet) rješenje dvaju problema koristeći simplex metodu (slično kao applet rješenje) s detaljnim objašnjenjima kako bi se razumio algoritam za rješavanje problema. Prvi zadatak sadrži znakove nejednakosti samo “≤” (problem s početnom bazom), drugi može sadržavati znakove “≥”, “≤” ili “=” (problem s umjetnom bazom), različito se rješavaju.

Simpleksna metoda, rješavanje problema s početnom bazom

1)Simpleks metoda za problem s početnom bazom (svi znakovi nejednakosti ograničenja " ≤ ").

Upišimo problem kanonski obliku, tj. prepisujemo ograničenja nejednakosti u obliku jednakosti, dodajući bilanca stanja varijable:

Ovaj sustav je sustav s bazom (baze s 1, s 2, s 3, svaka od njih je uključena u samo jednu jednadžbu sustava s koeficijentom 1), x 1 i x 2 su slobodne varijable. Problemi koji se rješavaju simpleks metodom moraju imati sljedeća dva svojstva:
-sustav ograničenja mora biti sustav jednadžbi s bazom;
-slobodni članovi svih jednadžbi u sustavu moraju biti nenegativni.

Rezultirajući sustav je sustav s bazom i njegovi slobodni članovi su nenegativni, pa se može primijeniti simpleks metoda. Kreirajmo prvu simpleks tablicu (iteracija 0), tj. tablicu koeficijenata funkcije cilja i sustav jednadžbi za pripadajuće varijable. Ovdje "BP" znači stupac osnovnih varijabli, "Rješenje" znači stupac desnih strana jednadžbi sustava. Rješenje nije optimalno, jer postoje negativni koeficijenti u z-retku.

iteracija 0

Kako bismo poboljšali rješenje, prelazimo na sljedeću iteraciju i dobivamo sljedeću simpleks tablicu. Da biste to učinili, morate odabrati omogućiti stupac, tj. varijabla koja će biti uključena u bazu u sljedećoj iteraciji. Odabire se prema najvećem apsolutnom negativnom koeficijentu u z-retku (u maksimalnom problemu) - u početnoj iteraciji to je stupac x 2 (koeficijent -6).

Zatim odaberite omogućiti niz, tj. varijabla koja će napustiti bazu u sljedećoj iteraciji. Odabire se najmanjim omjerom stupca “Odluka” prema odgovarajućim pozitivnim elementima stupca rezolucije (stupac “Omjer”) - u početnoj iteraciji to je red s 3 (koeficijent 20).

Permisivni element nalazi se na sjecištu razlučujućeg stupca i razlučujućeg retka, njegova ćelija je označena bojom, jednaka je 1. Stoga će u sljedećoj iteraciji varijabla x 2 zamijeniti s 3 u bazi. Imajte na umu da se odnos ne traži u z-stringu; tamo se stavlja crtica "-". Ako postoje identični minimalni odnosi, odabire se bilo koji od njih. Ako su svi koeficijenti u stupcu rezolucije manji ili jednaki 0, tada je rješenje problema beskonačno.

Ispunimo sljedeću tablicu “Iteracija 1”. Dobit ćemo ga iz tablice “Iteration 0”. Cilj daljnjih transformacija je pretvoriti stupac rezolucije x2 u stupac jedinice (s jedinicom umjesto elementa rezolucije i nulama umjesto preostalih elemenata).

1) Izračunajte redak x 2 tablice "Iteracija 1". Prvo, podijelimo sve članove razrješavajućeg retka s 3 tablice "Iteracija 0" s razlučujućim elementom (u ovom slučaju je jednak 1) ove tablice, dobivamo redak x 2 u tablici "Iteracija 1" . Jer razlučujući element u ovom slučaju jednak je 1, tada će se red s 3 tablice "Iteracija 0" podudarati s retkom x 2 tablice "Iteracija 1". Redak x 2 tablice "Iteracija 1" primili smo 0 1 0 0 1 20, preostali redovi tablice "Iteracija 1" dobit će se iz ovog retka i redaka tablice "Iteracija 0" kako slijedi:

2) Izračun z-retka tablice "Iteracija 1". Umjesto -6 u prvom retku (z-redak) u stupcu x2 tablice Iteracije 0, treba postojati 0 u prvom retku tablice Iteracije 1. Da biste to učinili, pomnožite sve elemente retka x 2 tablice "Iteracija 1" 0 1 0 0 1 20 sa 6, dobit ćemo 0 6 0 0 6 120 i zbrojite ovaj red s prvim redom (z - red) tablice "Iteracija 0" -4 -6 0 0 0 0, dobivamo -4 0 0 0 6 120. U stupcu x 2 pojavljuje se nula 0, cilj je postignut. Elementi stupca rezolucije x 2 označeni su crvenom bojom.

3) Izračun retka s 1 tablice "Iteracija 1". Umjesto 1 u prvom retku tablice "Iteracija 0" trebala bi stajati 0 u tablici "Iteracija 1". Da biste to učinili, pomnožite sve elemente retka x 2 tablice "Iteracija 1" 0 1 0 0 1 20 s -1, dobijete 0 -1 0 0 -1 -20 i dodajte ovaj red sa s 1 - redom tablici "Iteration 0" 2 1 1 0 0 64, dobivamo redak 2 0 1 0 -1 44. U stupcu x 2 dobivamo traženu 0.

4) Izračunajte red s 2 u tablici "Iteracija 1". Na mjestu 3 u s 2 retku tablice "Iteracija 0" treba biti 0 u tablici "Iteracija 1". Da biste to učinili, pomnožite sve elemente retka x 2 tablice “Iteracija 1” 0 1 0 0 1 20 s -3, dobijete 0 -3 0 0 -3 -60 i dodajte ovaj red sa s 2 - retkom tablice “Iteracija 0” 1 3 0 1 0 72, dobivamo redak 1 0 0 1 -3 12. U stupcu x 2 dobivena je tražena 0. Stupac x 2 u tablici “Iteracija 1” postao je jedinica , sadrži jednu 1, a ostatak 0.

Redovi tablice "Iteracija 1" dobivaju se prema sljedećem pravilu:

Novi redak = Stari redak – (koeficijent stupca rezolucije starog retka)*(Novi redak rezolucije).

Na primjer, za z-string imamo:

Stari z-string (-4 -6 0 0 0 0)
-(-6)*Nova linija rezolucije -(0-6 0 0 -6 -120)
=Novi z-string(-4 0 0 0 6 120) .

Za sljedeće tablice preračunavanje elemenata tablice radi se na sličan način, pa ga izostavljamo.

ponavljanje 1

Razrješavanje stupca x 1, razrješavanje reda s 2, s 2 izlazi iz baze, x 1 ulazi u bazu. Na potpuno isti način dobivamo preostale simpleks tablice dok ne dobijemo tablicu sa svim pozitivnim koeficijentima u z-retku. Ovo je znak optimalne tablice.

Ponavljanje 2

Razrješavajući stupac s 3, razrješavajući red s 1, s 1 izlazi iz baze, s 3 ulazi u bazu.

Ponavljanje 3

U z-retku svi koeficijenti su nenegativni, pa je dobiveno optimalno rješenje x 1 = 24, x 2 = 16, z max = 192.

Simpleksna metoda, rješavanje problema s umjetnom osnovom

2) Riješimo problem s umjetnom osnovom (barem jedan znak ograničenja nejednakosti “≥” ili “=”).

Napišimo problem u kanonskom obliku (u obliku sustava jednadžbi, koji zahtijeva simpleks metodu), da bismo to učinili uvodimo dvije varijable x 3 ≥ 0 i x 4 ≥ 0, dobivamo:

Sustav ograničenja nudi samo jednu dopuštenu osnovnu varijablu x 4, samo što je ona uključena u samo jednu jednadžbu u trećoj s koeficijentom 1, pa prvoj i drugoj jednadžbi dodajemo umjetne varijable R 1 ≥ 0 i R 2 ≥ 0 kako bi se mogla primijeniti simpleks metoda, jednadžbe ograničenja sustava moraju biti sustav s bazom, tj. u svakoj jednadžbi mora postojati varijabla s koeficijentom 1, koja je uključena u samo jednu jednadžbu sustava, u našem slučaju to su R 1, R 2 i x 4. Dobili smo tzv. M-zadatak:

Ovaj sustav je sustav s bazom, u kojem su R 1, R 2 i x 4 osnovne varijable, a x 1, x 2 i x 3 slobodne varijable, slobodni članovi svih jednadžbi su nenegativni. Stoga se za rješavanje problema može koristiti simpleks metoda. Zapišimo početnu simpleks tablicu:

iteracija 0

U tablicu je dodan redak "Evaluacija" za probleme s umjetnom osnovom. Dobiva se zbrajanjem odgovarajućih koeficijenata redaka s umjetnim varijablama (R) suprotnog predznaka. Bit će prisutan u tablici sve dok je barem jedna od umjetnih varijabli u bazi. Na temelju najvećeg modulo negativnog koeficijenta retka “Ocjena” određuje se razrješavajući stupac dok je u tablici. Kada redak "Vrednovanje" napusti tablicu (nema umjetnih varijabli u bazi), razrješavajući stupac će biti određen z-redom, kao u problemu s početnom bazom. U ovoj tablici, stupac za rješavanje je x 2, odabire se na temelju najvećeg apsolutnog negativnog rezultata (-7). Razrješavajući red R 2 odabire se na temelju najmanjeg omjera stupca "Rješenje" prema odgovarajućim pozitivnim elementima razrješujućeg stupca, kao u problemu bez umjetnih varijabli. To znači da će u sljedećoj iteraciji varijabla x2 prijeći iz slobodne u osnovnu, a varijabla R2 iz osnovne u slobodnu. Napišimo sljedeću simpleks tablicu:

Razrješavanje stupca x 1, razrješavanje reda R 1, R 1 izlazi iz baze, x 1 ulazi u bazu. Nakon toga u osnovi nema preostalih umjetnih varijabli, tako da u sljedećoj tablici nema retka "Ocjena":

ponavljanje 2

Zatim je stupac razlučivosti odabran z-redkom. U z-retku svi koeficijenti su nenegativni osim koeficijenta za umjetnu varijablu R 1, koji ne utječe na optimalnost kada umjetne varijable napuste bazu. Posljedično, dobiva se optimalno rješenje x 1 = 6/5; x 2 = 3/5; z max = 72/5.

Posebni slučajevi korištenja simpleks metode

1) Kada je ravna linija (ako se razmatra problem dvodimenzionalnog linearnog programiranja, au općem slučaju hiperravnina) koja predstavlja ciljnu funkciju paralelna s ravnom linijom (hiperravninom) koja odgovara jednom od ograničenja nejednakosti (koje na optimalna točka zadovoljena kao točna jednakost), funkcija cilja uzima jednu i također je optimalna vrijednost na određenom skupu točaka na granici područja mogućih rješenja. Ta se rješenja nazivaju alternativna optimalna rješenja. Prisutnost alternativnih rješenja može se odrediti pomoću optimalne simpleks tablice. Ako z-redak optimalne tablice sadrži nula koeficijenata nebazičnih varijabli, tada postoje alternativna rješenja.

2) Ako su u razlučujućem stupcu simpleks tablice svi koeficijenti manji ili jednaki nuli, tada je nemoguće odabrati razlučujući red, u ovom slučaju rješenje je neograničeno.

3) Ako su ograničenja problema linearnog programiranja nekonzistentna (to jest, ne mogu biti zadovoljena istovremeno), tada problem nema izvediva rješenja. Ova situacija ne može nastati ako su sve nejednakosti koje čine sustav ograničenja tipa “≤” s nenegativnim desnim stranama, jer u ovom slučaju, dodatne varijable mogu predstavljati izvedivo rješenje. Za druge vrste ograničenja koriste se umjetne varijable. Ako problem ima rješenje, tada u optimalnoj tablici nema umjetnih varijabli (R i) u bazi. Ako su tu, onda problem nema rješenja.

Konac, gumbi i tkanina koriste se za izradu tri vrste košulja. Zalihe konca, gumba i tkanine, norme njihove potrošnje za šivanje jedne košulje navedene su u tablici. Pronaći maksimalnu dobit i optimalni plan proizvodnje proizvoda koji to osigurava (naći).

Rješenje problema

Izgradnja modela

Kroz i broj košulja 1., 2. i 3. vrste namijenjenih za puštanje.

Tada će ograničenja resursa izgledati ovako:

Štoviše, prema značenju zadatka

Ciljna funkcija koja izražava dobivenu dobit:

Dobivamo sljedeći problem linearnog programiranja:

Svođenje problema linearnog programiranja na kanonski oblik

Svedimo problem na kanonski oblik. Uvedimo dodatne varijable. Sve dodatne varijable uvodimo u funkciju cilja s koeficijentom jednakim nuli. Lijevim stranama restrikcija dodajemo dodatne varijable koje nemaju preferirani oblik i dobivamo jednakosti.

Rješavanje problema simpleks metodom

Ispunite simpleks tablicu:

Budući da problem rješavamo do maksimuma, prisutnost negativnih brojeva u retku indeksa pri rješavanju problema do maksimuma ukazuje na to da nismo dobili optimalno rješenje i da je potrebno prijeći s tablice 0. iteracije na sljedeći.

Nastavljamo sa sljedećom iteracijom na sljedeći način:

vodeći stupac odgovara

Ključni red određen je minimalnim omjerom slobodnih članova i članova vodećeg stupca (simpleksni odnosi):

Na sjecištu ključnog stupca i ključnog retka nalazimo element omogućavanja, tj. 9.

Sada prelazimo na sastavljanje 1. iteracije: Umjesto jediničnog vektora, uvodimo vektor .

U novoj tablici umjesto omogućavajućeg elementa pišemo 1, svi ostali elementi ključnog stupca su nule. Ključni elementi niza podijeljeni su na element enable. Svi ostali elementi tablice izračunavaju se prema pravilu pravokutnika.

Ključni stupac za 1. ponavljanje odgovara

Razlučujući element je broj 4/3. Vektor izvodimo iz baze i umjesto nje uvodimo vektor. Dobivamo tablicu 2. iteracije.

Ključni stupac za 2. ponavljanje odgovara

Pronalazimo ključnu liniju, za to definiramo:

Razlučujući element je broj 10/3. Vektor izvodimo iz baze i umjesto nje uvodimo vektor. Dobivamo tablicu 3. iteracije.

U indeksnom redu svi članovi su nenegativni, pa se dobiva sljedeće rješenje problema linearnog programiranja (ispisujemo ga iz stupca slobodnih članova):

Potrebno je sašiti 24 košulje 1. vrste, 7 košulja 2. vrste i 3 košulje 3. vrste. U tom će slučaju dobivena dobit biti maksimalna i iznositi 95 rubalja.

Linearno programiranje je tehnika matematičkog modeliranja dizajnirana za optimizaciju korištenja ograničenih resursa. LP se uspješno koristi u vojnom polju, industriji, poljoprivreda, prometnoj industriji, gospodarstvu, zdravstvenom sustavu pa čak i in društvenih znanosti. Široku primjenu ove metode podupiru i visoko učinkoviti računalni algoritmi koji implementiraju ovu metodu. Optimizacijski algoritmi za druge, složenije vrste modela i problema operacijskog istraživanja (OR), uključujući cjelobrojno, nelinearno i stohastičko programiranje, temelje se na algoritmima linearnog programiranja.

Problem optimizacije je ekonomsko-matematički problem koji se sastoji od pronalaženja optimalne (maksimalne ili minimalne) vrijednosti funkcije cilja, a vrijednosti varijabli moraju pripadati određenom rasponu prihvatljivih vrijednosti.

U svom najopćenitijem obliku, problem linearnog programiranja je matematički napisan na sljedeći način:

Gdje X = (x 1 , x 2 , ... , x n ) ; W– raspon dopuštenih vrijednosti varijabli x 1 , x 2 , ... , x n ;f(X)– objektivna funkcija.

Da bi se riješio optimizacijski problem, dovoljno je pronaći njegovo optimalno rješenje, tj. naznačiti da u bilo kojem .

Optimizacijski problem je nerješiv ako nema optimalno rješenje. Konkretno, problem maksimizacije bit će nerješiv ako funkcija cilja f(X) nije omeđen odozgo na dopustivom skupu W.

Metode rješavanja optimizacijskih problema ovise o vrsti funkcije cilja f(X), te iz strukture dopustivog skupa W. Ako je ciljna funkcija u problemu funkcija n varijabli, tada se metode rješenja nazivaju metodama matematičkog programiranja.

Karakteristične značajke problema linearnog programiranja su sljedeće:

indeks optimalnosti f(X) je linearna funkcija elemenata rješenja X = (x 1 , x 2 , ... , x n ) ;

restriktivni uvjeti nametnuti mogućim rješenjima poprimaju oblik linearnih jednakosti ili nejednakosti.

Problem linearnog programiranja naziva se problem operacijskog istraživanja, čiji matematički model ima oblik:

(2) (3) (4) (5)

Istovremeno, sustav linearne jednadžbe(3) i nejednakosti (4), (5), što određuje dopušteni skup rješenja problema W, nazvao sustav ograničenja problemi linearnog programiranja i linearna funkcija f(X) nazvao ciljna funkcija ili kriterij optimalnosti .

Valjano rješenje je zbirka brojeva ( plan ) X = (x 1 , x 2 , ... , x n ) , zadovoljavajući ograničenja problema. Optimalno rješenje – ovo je plan u kojem funkcija cilja poprima svoju maksimalnu (minimalnu) vrijednost.

Ako matematički model problema linearnog programiranja ima oblik:

onda kažu da je problem predstavljen u kanonski oblik .

Svaki problem linearnog programiranja može se svesti na problem linearnog programiranja u kanonskom obliku. Da biste to učinili, u općem slučaju, morate biti u stanju smanjiti problem maksimizacije na problem minimizacije; prijeđite s ograničenja nejednakosti na ograničenja jednakosti i zamijenite varijable koje ne poštuju uvjet nenegativnosti. Maksimiziranje određene funkcije je jednako minimiziranju iste funkcije uzete sa suprotnim predznakom, i obrnuto.

Pravilo za dovođenje problema linearnog programiranja u kanonski oblik je sljedeće:

ako je u izvornom zadatku potrebno odrediti maksimum linearne funkcije, tada treba promijeniti predznak i tražiti minimum te funkcije;

ako je desna strana ograničenja negativna, tada to ograničenje treba pomnožiti s -1;

ako među ograničenjima postoje nejednakosti, onda se uvođenjem dodatnih nenegativnih varijabli one pretvaraju u jednakosti;

ako neka varijabla x j nema ograničenja predznaka, tada se zamjenjuje (u funkciji cilja i u svim ograničenjima) razlikom između dvije nove ne-negativne varijable: x 3 = x 3 + - x 3 - , Gdje x 3 + , x 3 - ≥ 0 .

Primjer 1. Svođenje problema linearnog programiranja na kanonski oblik:

min L = 2x 1 + x 2 - x 3 ; 2x 2 - x 3 ≤ 5; x 1 + x 2 - x 3 ≥ -1; 2x 1 - x 2 ≤ -3; x 1 ≤ 0; x 2 ≥ 0; x 3 ≥ 0.

Uvedimo izravnavajuće varijable u svaku jednadžbu sustava ograničenja x 4 , x 5 , x 6 . Sustav ćemo napisati u obliku jednakosti, au prvoj i trećoj jednadžbi sustava ograničenja varijable x 4 , x 6 ulaze u lijeva strana sa znakom "+", a u drugoj jednadžbi varijabla x 5 upisuje se sa znakom "-".

2x 2 - x 3 + x 4 = 5; x 1 + x 2 - x 3 - x 5 = -1; 2x 1 - x 2 + x 6 = -3; x 4 ≥ 0; x 5 ≥ 0; x 6 ≥ 0.

Slobodni članovi u kanonskom obliku moraju biti pozitivni, pomnožite posljednje dvije jednadžbe s -1:

2x 2 - x 3 + x 4 = 5; -x 1 - x 2 + x 3 + x 5 = 1; -2x 1 + x 2 - x 6 = 3.

Simpleksna metoda za rješavanje problema linearnog programiranja.

Algoritam simpleksne metode pronalazi optimalno rješenje uzimajući u obzir ograničeni broj izvedivih osnovnih rješenja. Algoritam simpleksne metode uvijek počinje s nekim izvedivim baznim rješenjem i zatim pokušava pronaći drugo izvedivo bazno rješenje koje "poboljšava" vrijednost funkcije cilja. To je jedino moguće ako povećanje bilo koje nulte (nebazne) varijable dovodi do poboljšanja vrijednosti funkcije cilja. Ali da bi nebazična varijabla postala pozitivna, jedna od trenutnih osnovnih varijabli mora biti postavljena na nulu, tj. pretvoriti u neosnovne. To je neophodno kako bi novo rješenje točno sadržavalo m osnovne varijable. U skladu s terminologijom simpleks metode poziva se odabrana nula varijabla ulazni (na bazu), a varijabla baze koju treba izbrisati je isključeni (od osnove).

Nazovimo dva pravila za odabir ulaznih i isključenih varijabli u simpleks metodi uvjet optimalnosti I uvjet dopuštenosti . Formulirajmo ova pravila i također razmotrimo redoslijed radnji koje se izvode pri implementaciji simpleks metode.

Uvjet optimalnosti. Ulazna varijabla u problemu maksimizacije (minimizacije) je nebazična varijabla koja ima najveći negativni (pozitivni) koeficijent u cilj- linija. Ako u cilj-linija sadrži više takvih koeficijenata, tada se odabir unesene varijable vrši proizvoljno. Optimalno rješenje se postiže kada cilj-linija, svi koeficijenti za nebazične varijable bit će nenegativni (nepozitivni).

Uvjet prihvatljivosti. U problemima maksimizacije i minimizacije, bazna varijabla za koju je omjer vrijednosti desne strane ograničenja minimalan i pozitivnog koeficijenta vodećeg stupca odabrana je kao isključena. Ako postoji više osnovnih varijabli s ovim svojstvom, tada je izbor isključene varijable proizvoljan.

Predstavimo algoritam za rješavanje problema linearnog programiranja pronalaženja maksimuma pomoću simpleks tablica.

F = s 1 x 1 +s 2 x 2 +…+s n x n max

x 1 0, x 2 0,…, x n 0.

1. korak. Uvodimo dodatne varijable i zapisujemo dobiveni sustav jednadžbi i linearnu funkciju u obliku proširenog sustava.

F–c 1 x 1 –c 2 x 2 –…–c n x n =0=c str.

2. korak. Sastavljamo početnu simpleks tablicu.

3. korak. Provjeravamo ispunjenje kriterija optimalnosti - prisutnost negativnih koeficijenata u zadnjem retku. Ako ih nema, tada je rješenje optimalno i F * =c o, osnovne varijable su jednake odgovarajućim koeficijentima b j, nebazične varijable su jednake nuli, tj. X * =(b 1,b 2,…, b m, 0,…, 0).

4. korak. Ako kriterij optimalnosti nije zadovoljen, tada najveći apsolutni negativni koeficijent u zadnjem (procijenjenom) retku određuje razlučujući stupac s.

Da bismo odredili liniju rezolucije, izračunavamo omjere procjene i ispunite zadnji stupac tablice.

Procijenjeni omjer i-tog reda je

 ako je b i i a ima različite znakove;

 ako je b i =0 i a je<0;

 ako je a =0;

0 ako b i =0 i a je >0;

U stupcu evaluacijskih odnosa nalazimo minimalni element min koji definira omogućavajući niz g.

Ako ne postoji minimum, onda problem nema konačni optimum I i nerješiv je.

Na sjecištu razlučujućeg retka i stupca nalazi se razlučujući element a gs.

5. korak. Napravimo sljedeću tablicu. Za ovo

Prijeđimo na treći korak.

M-metoda Ponekad, prilikom rješavanja ZLP-a, matrica koeficijenata za nepoznata ograničenja sustava nema jedinične stupce iz kojih se može sastaviti jedinična matrica, tj. javlja se problem u izboru baznih varijabli ili je početno rješenje neprihvatljivo. U takvim slučajevima koristite metoda umjetne osnove (M - metoda). U svim ograničenjima gdje nema osnovnih varijabli, umjetne varijable. U funkciju cilja uvode se umjetne varijable s koeficijentom (- M) za probleme s max i s koeficijentom (+ M) za probleme s min, gdje je M dovoljno velik pozitivan broj. Zatim se prošireni problem rješava prema pravilima simpleks metode. Ako su sve umjetne varijable jednake nuli, tj. isključeni iz baze, tada će se ili dobiti optimalno rješenje izvornog problema, ili se izvorni problem dalje rješava i pronalazi njegovo optimalno rješenje ili se utvrđuje njegova nerješivost. Ako se barem jedna od umjetnih varijabli pokaže različitom od nule, tada izvorni problem nema rješenja

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

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

Algoritam simpleks metode za rješavanje problema linearnog programiranja

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

Primjer rješavanja zadatka simpleks metodom

Zadatak riješite simpleks metodom:

Otopina:

Problem dovodimo u kanonski oblik.

Da bismo to učinili, uvodimo dodatnu varijablu x 6 s koeficijentom +1 na lijevu stranu prvog ograničenja nejednakosti. Varijabla x 6 uključena je u funkciju cilja s koeficijentom nula (tj. nije uključena).

Dobivamo:

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

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

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

Δ k = C b X k - c k

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

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

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

U zadnjem retku tablice s procjenama Δ k u stupcu "A 0" napisane su vrijednosti funkcije cilja na referentnom rješenju Z(X 1).

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

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

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

Prirast funkcije cilja nalazi se po formuli: .

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

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

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

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

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

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

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

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

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

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

Metoda linearnog programiranja u ekonomskoj analizi

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

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

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

Vrlo je uobičajeno rješavati takozvani problem transporta metodom linearnog programiranja. Sadržaj ovog zadatka je minimiziranje troškova koji nastaju u vezi s operacijom vozila uz postojeća ograničenja u pogledu broja vozila, njihove nosivosti, trajanja njihovog rada, te ako postoji potreba za održavanjem maksimalna količina kupaca.

Osim toga, ova metoda se široko koristi u rješavanju problema rasporeda. Ovaj zadatak sastoji se od takve raspodjele radnog vremena za osoblje određene organizacije koja bi bila najprihvatljivija kako za članove ovog osoblja tako i za klijente organizacije.

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

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

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

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

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

Dinamičko programiranje temelji se na konstruiranju stabla odlučivanja. Svaki sloj ovog stabla služi kao pozornica za određivanje posljedica prethodne odluke i za eliminiranje neučinkovitih opcija za tu odluku. Dakle, dinamičko programiranje ima višestupanjsku prirodu. Ova vrsta programiranja koristi se u ekonomskoj analizi za pronalaženje optimalnih opcija za razvoj organizacije sada iu budućnosti.

Konveksno programiranje je vrsta nelinearnog programiranja. Ova vrsta programiranja izražava nelinearnu prirodu odnosa između rezultata aktivnosti organizacije i njezinih troškova. Konveksno (aka konkavno) programiranje analizira konveksne ciljne funkcije i konveksne sustave ograničenja (točke izvedivosti). Konveksno programiranje primijenjeno u analizi gospodarska djelatnost kako bi se minimizirali troškovi, a konkavni - kako bi se maksimizirao prihod uz postojeća ograničenja na djelovanje čimbenika koji na analizirane pokazatelje utječu suprotno. Posljedično, s vrstama programiranja koje se razmatraju, konveksne ciljne funkcije su minimizirane, a konkavne ciljne funkcije su maksimizirane.