TEMA: LINEARNO PROGRAMIRANJE

ZADATAK 2.A. Rješavanje problema linearnog programiranja grafička metoda

Pažnja!

Ovo je PROBNA VERZIJA rada br. 2073, cijena originala je 200 rubalja. Dizajnirano u Microsoft program Riječ.

Plaćanje. Kontakti.

Opcija 7. Pronađite maksimalnu i minimalnu vrijednostlinearna funkcija F = 2x 1 - 2 x 2sa ograničenjima: x 1 + x 2 ≥ 4;

- x 1 + 2 x 2 ≤ 2;

x 1 + 2 x 2 ≤ 10;

x i ≥ 0, i = 1.2.

Rješenje:

Uslovnom zamjenom znakova nejednakosti predznacima jednakosti dobijamo sistem jednačina x1 + x2 = 4;

- x1 + 2 x2 = 2;

x1 + 2 x2 = 10.

Konstruirajmo prave koristeći ove jednačine, zatim u skladu sa predznacima nejednačina odaberemo poluravnine i dobijemo njihov zajednički dio - područje dopuštenih rješenja ODR - četverougao MNPQ.

Minimalna vrijednost funkcije

cije - u tački M(2; 2)

F min = 2·2 - 2·2 = 0.

Maksimalna vrijednost se postiže u tački N (10; 0),

F max = 2·10 - 2·0 = 20.

Opcija 8. Pronađite maksimalnu i minimalnu vrijednost

linearna funkcija F = x 1 + x 2

sa ograničenjima: x 1 - 4 x 2 - 4 ≤ 0;

3 x 1 - x 2 ≥ 0;

x 1 + x 2 - 4 ≥ 0;

x i ≥ 0, i = 1.2.

Rješenje:

Uslovnom zamjenom znakova nejednakosti znakovima jednakosti dobijamo sistem jednačina x1 - 4 x2 = 4 ;

3 x1 - x2 = 0;

Konstruirajmo prave koristeći ove jednačine, zatim u skladu sa predznacima nejednakosti odaberemo poluravnine i dobijemo njihov zajednički dio - područje dopuštenih rješenja ODR - neograničeni poligon MNPQ.

Minimalna vrijednost funkcije

cije – na direktnom NP, na primjer

u tački P(4; 0)

F min = 4 + 0 = 4.

ODR nije ograničen odozgo, stoga je F max = + ∞.

Opcija 10. Pronađite maksimalnu i minimalnu vrijednost

linearna funkcija F = 2 x 1 - 3 x 2

sa ograničenjima: x 1 + 3 x 2 ≤ 18;

2 x 1 + x 2 ≤ 16;

x 2 ≤ 5;

x i ≥ 0, i = 1.2.

Uslovnom zamjenom znakova nejednakosti znakovima jednakosti dobijamo sistem jednadžbi

x 1 + 3 x 2 = 18 (1);

2 x 1 + x 2 = 16 (2);

3 x 1 = 21 (4).

Konstruirajmo prave koristeći ove jednačine, a zatim u skladu sa znacima nejednakosti odaberemo poluravnine i dobijemo njihov zajednički dio - područje dopuštenih rješenja ODR - poligon MNPQRS.

Konstruirajmo vektor G(2; -3) i povučemo kroz početak koordinata linija nivoa– ravno.

Pomeramo liniju nivoa u pravcu, vrednost F se povećava. U tački S(7; 0) ciljna funkcija dostiže maksimum F max =2·7–3·0= = 14. Pomeramo liniju nivoa u pravcu, vrednost F opada. Minimalna vrijednost funkcije je u tački N(0; 5)

F min = 2·0 – 3·5 = –15.

ZADATAK 2.B. Rješavanje problema linearnog programiranja

analitička simpleks metoda

Opcija 7. Minimizirajte funkciju cilja F = x 1 - x 2 + x 3 + x 4 + x 5 - x 6

sa ograničenjima: x 1 + x 4 +6 x 6 = 9,

3 x 1 + x 2 – 4 x 3 + 2 x 6 = 2,

x 1 + 2 x 3 + x 5 + 2 x 6 = 6.

Rješenje:

Broj nepoznanica n=6, broj jednačina m=3. Stoga se r = n-m = 3 nepoznate mogu uzeti kao slobodne. Odaberimo x 1, x 3 i x 6.

Osnovne varijable x 2 , x 4 i x 5 izražavamo u terminima slobodnih i svedemo sistem na jediničnu osnovu

x 2 = 2 – 3 x 1 + 4 x 3 – 2 x 6

x 4 = 9 – x 1 – 6 x 6 (*)

x 5 = 6 – x 1 – 2 x 3 – 2 x 6

Ciljna funkcija će izgledati ovako:

F = x 1 - 2 + 3 x 1 - 4 x 3 + 2 x 6 + x 3 + 9 – x 1 – 6 x 6 +6 – x 1 – 2 x 3 – 2 x 6 – x 6 =

13 + 2 x 1 – 5 x 3 – 7 x 6

Stavimo x 1 = x 3 = x 6 = 0, a osnovne varijable će poprimiti vrijednosti x 2 = 2; x 4 = 9; x 5 = 6, odnosno prvo moguće rješenje (0; 2; 0; 9; 6; 0), ciljna funkcija F 1 = 13.

Varijable x 3 i x 6 uključene su u ciljnu funkciju sa negativnim koeficijentima, stoga, kako se njihove vrijednosti povećavaju, vrijednost F će se smanjiti. Uzmimo za primjer x 6. Iz 1. jednačine sistema (*) jasno je da je povećanje vrijednosti x 6 moguće do x 6 = 1 (dok je x 2 ³ 0). U ovom slučaju, x 1 i x 3 ostaju jednaki nuli. Sada uzimamo x 4, x 5, x 6 kao osnovne varijable, a x 1, x 2, x 3 kao slobodne varijable. Izrazimo nove osnovne varijable u terminima novih slobodnih. Dobijamo

x 6 = 1 – 3/2 x 1 – 1/2 x 2 + 2 x 3

x 4 = 3 + 8 x 1 + 3 x 2 – 12 x 3

x 5 = 4 + 2 x 1 + x 2 – 6 x 3

F = 6 + 25/2 x 1 + 7/2 x 2 – 19 x 3

Dodijelimo nulte vrijednosti slobodnim varijablama, odnosno x 1 = x 2 = x 3 = 0, dok je x 6 = 1, x 4 = 3, x 5 = 4, odnosno treće izvodljivo rješenje (0 0; U ovom slučaju F 3 = 6.

Varijabla x 3 je uključena u funkciju cilja sa negativnim koeficijentom, stoga će povećanje x 3 u odnosu na nultu vrijednost dovesti do smanjenja F. Iz 2. jednačine je jasno da se x 3 može povećati na 1/4 , iz 3. jednačine - do 2/3 . Druga jednačina je kritičnija. Pretvorimo varijablu x 3 u broj osnovnih, a x 4 u broj slobodnih.

Sada uzimamo x 1, x 2 i x 4 kao nove slobodne varijable. Izrazimo kroz njih nove osnovne varijable x 3, x 5, x 6. Idemo po sistem

x 3 = 1/4 + 2/3 x 1 + 1/4 x 2 – 1/12 x 4

x 5 = 5/2 – 2 x 1 – 1/2 x 2 + 1/2 x 4

x 6 = 3/2 – 1/6 x 1 – 1/6 x 4

Ciljna funkcija će poprimiti oblik

F = 5/4 - 1/6 x 1 - 5/4 x 2 + 19/12 x 4

Varijable x 1 i x 2 uključene su u ciljnu funkciju sa negativnim koeficijentima, stoga, kako se njihove vrijednosti povećavaju, vrijednost F će se smanjiti. Uzmimo za primjer x 2. Iz 2. jednačine sistema jasno je da je povećanje vrijednosti x 2 moguće do x 2 = 5 (dok je x 5 ³ 0). U ovom slučaju, x 1 i x 4 ostaju nula, vrijednosti ostalih varijabli su jednake x 3 = 3/2; x 5 = 0, x 6 = 3/2, odnosno četvrto izvodljivo rješenje (0; 5; 3/2; 0; 0; 3/2). U ovom slučaju F 4 = 5/4.

Sada uzimamo x 1, x 4 i x 5 kao nove slobodne varijable. Izrazimo kroz njih nove osnovne varijable x 2, x 3, x 6. Idemo po sistem

x 2 = 5 – 4 x 1 + x 4 – 2 x 5

x 3 = 3/2 – 1/3 x 1 + 1/6 x 4 – 1/2 x 5

x 6 = 3/2 – 1/6 x 1 – 1/6 x 4

Ciljna funkcija će poprimiti oblik

F = - 5 + 29/6 x 1 + 1/3 x 4 + 5/2 x 5

Koeficijenti za obje varijable u izrazu za F su pozitivni, pa je dalje smanjenje vrijednosti F nemoguće.

Odnosno, minimalna vrijednost F min = - 5, posljednje moguće rješenje (0; 5; 3/2; 0; 0; 3/2) je optimalno.

Opcija 8. Maksimizirajte funkciju cilja F = 4 x 5 + 2 x 6

sa ograničenjima: x 1 + x 5 + x 6 = 12;

x 2 + 5 x 5 - x 6 = 30;

x 3 + x 5 - 2 x 6 = 6;

2 x 4 + 3 x 5 - 2 x 6 = 18;

Rješenje:

Broj jednačina je 4, broj nepoznatih je 6. Dakle, r = n – m = 6 – 4 = 2 varijable se mogu izabrati kao slobodne varijable, 4 varijable kao osnovne. Odaberemo x 5 i x 6 kao slobodne, a x 1 , x 2 , x 3 , x 4 kao osnovne. Izrazimo osnovne varijable u terminima slobodnih i svedemo sistem jednačina na jediničnu osnovu

x 1 = 12 - x 5 - x 6 ;

x 2 = 30 - 5 x 5 + x 6 ;

x 3 = 6 - x 5 + 2 x 6 ;

x 4 = 9 - 3/2 x 5 + x 6;

Ciljnu funkciju zapisujemo u obliku F = 4 x 5 + 2 x 6. Dodijelimo nulte vrijednosti slobodnim varijablama x 5 = x 6 = 0. U ovom slučaju, osnovne varijable će poprimiti vrijednosti x 1 = 12, x 2 = 30, x 3 = 6, x 4 = 9 , odnosno dobijamo prvo izvodljivo rješenje (12, 30 , 6, 9, 0,) i F 1 = 0.

Obje slobodne varijable ulaze u funkciju cilja s pozitivnim koeficijentima, odnosno moguće je daljnje povećanje F. Pretvorimo, na primjer, x 6 u broj osnovnih. Iz jednačine (1) je jasno da je x 1 = 0 pri x 5 = 12, u (2) ÷ (4) x 6 uključeno sa pozitivnim koeficijentima. Pređimo na novu osnovu: osnovne varijable - x 6, x 2, x 3, x 4, slobodno - x 1, x 5. Izrazimo nove osnovne varijable u terminima novih slobodnih

x 6 = 12 - x 1 - x 5;

x 2 = 42 - x 1 - 6 x 5;

x 3 = 30 - 2 x 1 - 3 x 5 ;

x 4 = 21 - x 1 - 5/2 x 5 ;

Funkcija cilja će imati oblik F = 24 - 2 x 1 + 2 x 5 ;

Dodijelimo nulte vrijednosti slobodnim varijablama x 1 = x 5 = 0. U ovom slučaju, osnovne varijable će poprimiti vrijednosti x 6 = 12, x 2 = 42, x 3 = 30, x 4 = 21 , odnosno dobijamo drugo izvodljivo rješenje (0, 42 , 30, 21, 0, 12) i F 2 = 24.

Ciljna funkcija x 5 je uključena sa pozitivnim koeficijentom, odnosno moguć je dalji porast F. Pređimo na novu osnovu: osnovne varijable - x 6, x 5, x 3, x 4, slobodno - x 1. , x 2. Izrazimo nove osnovne varijable kroz new free

x 6 = 5 - 5/6 x 1 + 1/6 x 2;

x 5 = 7 - 1/6 x 1 - 1/6 x 2 ;

x 3 = 9 - 3/2 x 1 + 1/2 x 2 ;

x 4 = 7/2 - 7/12 x 1 + 5/12 x 5;

Funkcija cilja će imati oblik F = 38 – 7/2 x 1 – 1/3 x 2 ;

Dodijelimo nulte vrijednosti slobodnim varijablama x 1 = x 2 = 0. U ovom slučaju, osnovne varijable će poprimiti vrijednosti x 6 = 5, x 5 = 7, x 3 = 9, x 4 = 7 /2, odnosno dobijamo treće izvodljivo rješenje X 3 = (0, 0, 9, 7/2, 7, 5) i F 3 = 38.

Obje varijable ulaze u funkciju cilja sa negativnim koeficijentima, odnosno dalje povećanje F je nemoguće.

Stoga je posljednje izvodljivo rješenje optimalno, odnosno X opt = (0, 0, 9, 7/2, 7, 5) i F max = 38.

Opcija 10. Maksimizirajte ciljnu funkciju F = x 2 + x 3

sa ograničenjima: x 1 - x 2 + x 3 = 1,

x 2 - 2 x 3 + x 4 = 2.

Rješenje:

Sistem jednačina-ograničenja je konzistentan, jer su rangovi matrice sistema jednačina i proširene matrice isti i jednaki 2. Shodno tome, dvije varijable se mogu uzeti kao slobodne, a druge dvije varijable - osnovne - mogu se uzeti kao slobodne. biti izražen linearno u terminima dva slobodna.

Uzmimo x 2 i x 3 kao slobodne varijable Tada će osnovne varijable biti x 1 i x 2, koje ćemo izraziti u terminima slobodnih

x 1 = 1 + x 2 - x 3 ; (*)

x 4 = 2 - x 2 + 2 x 3 ;

Ciljna funkcija je već izražena u terminima x 2 i x 3, odnosno F = x 2 + x 3.

Za x 2 =0 i x 3 =0, osnovne varijable će biti jednake x 1 = 1, x 4 = 2.

Imamo prvo izvodljivo rješenje X 1 = (1, 0, 0, 2), sa F 1 = 0.

Povećanje F je moguće povećanjem, na primjer, vrijednosti x 3, koja je uključena u izraz za F sa pozitivnim koeficijentom (x 2 ostaje jednak nuli). Prva jednadžba sistema (*) pokazuje da se x 3 može povećati na 1 (iz uslova x 1 ³0), odnosno ova jednačina nameće ograničenje na povećanje vrijednosti x 3. Prva jednačina sistema (*) se rješava. Na osnovu ove jednačine prelazimo na novu bazu, zamjenjujući x 1 i x 3. Sada će osnovne varijable biti x 3 i x 4, a slobodne varijable će biti x 1 i x 2. Izrazimo sada x 3 i x 4 u terminima x 1 i x 2.

Dobijamo: x 3 = 1 - x 1 + x 2 ; (**)

x 4 = 4 - 2 x 1 + x 2 ;

F = x 2 + 1 - x 1 + x 2 = 1 - x 1 + 2 x 2

Izjednačavajući slobodne varijable sa nulom, dobijamo drugo dozvoljeno osnovno rešenje X 2 = (0; 0; 1; 4), za koje je F 2 = 1.

Povećanje F je moguće sa povećanjem x2. Povećanje x 2, sudeći po zadnjem sistemu jednačina (**), nije ograničeno. Shodno tome, F će poprimati sve veće pozitivne vrijednosti, odnosno F max = + ¥.

Dakle, ciljna funkcija F nije ograničena odozgo, stoga ne postoji optimalno rješenje.

ZADATAK 2.D. Sastavite zadatak dvojan zadatom

originalni zadatak.

Opcija 7. Maksimizirajte ciljnu funkciju F = 2× x 1 - x 4

sa ograničenjima: x 1 + x 2 = 20,

x 2 + 2× x 4 ≥ 5,

x 1 + x 2 + x 3 ≤ 8,

x i ≥ 0 (i = 1, 2, 3, 4)

Rješenje:

Dovedemo sistem ograničenja na jedan, na primjer, kanonski oblik, uvođenjem dodatnih varijabli u 2. i 3. jednadžbu

x 1 + x 2 = 20,

x 2 + 2 × x 4 – x 5 = 5,

- x 1 + x 2 + x 3 + x 6 = 8.

Dobili smo asimetrični problem tipa 2. Dvostruki problem će izgledati ovako:

Minimizirajte ciljnu funkciju F = 20 × y 1 + 5 × y2+8 × y 3

na y 1 - y 3 ≥ 2,

y 1 + y 2 + y 3 ≥ 0,

y 3 ≥ 0,

2× y 2 ≥ 1,

Y2 ≥ 0,

y 3 ≥ 0.

Opcija 8. Maksimizirajte funkciju cilja F = x 2 - x 4 - 3× x 5

sa ograničenjima: x 1 + 2× x 2 - x 4 + x 5 = 1,

— 4 × x 2 + x 3 + 2× x 4 - x 5 = 2,

3 × x 2 + x 5 + x 6 = 5,

x i ≥ 0, (i = 1, 6)

Rješenje:

Imamo početni problem maksimizacije sa sistemom ograničenja u obliku jednačina, odnosno, par dualnih problema ima asimetrični tip 2, čiji matematički model u matričnom obliku ima oblik:

Originalni problem: Dvostruki problem:

F = C × X max F = B T × Ymin

kod A × X = B na A T × Y ≥ C T

U originalnom problemu, red matrice koeficijenata za varijable u funkciji cilja ima oblik C = (0; 1; 0; -1; -3; 0),

matrica-kolona slobodnih termina i matrica koeficijenata za varijable u sistemu ograničenja imaju oblik

B = 2, A = 0 - 4 1 2 -1 0

Nađimo transponiranu matricu koeficijenata, matricu reda koeficijenata za varijable u funkciji cilja i matricu stupaca slobodnih termina

0 1 0 0 V T = (1; 2; 5)

A T = -1 2 0 C T = -1

Dvostruki problem će biti napisan u sljedećem obliku:

pronaći minimalnu vrijednost ciljne funkcije F = y 1 + 2 × y2+5 × y 3

pod ograničenjima y 1 ≥ 0,

2× y 1 - 4 × y2+3 × y 3 ≥ 1,

- y 1 + 2 × y 2 ≥ -1,

y 1 - y 2 + y 3 ≥ -3,

Opcija 10. Minimizirajte funkciju F = x 1 + x 2 + x 3

sa ograničenjima: 3× x 1 + 9× x 2 + 7× x 3 ≥ 2,

6 × x 1 + 4 x 2 + 5× x 3 ≥ 3,

8 × x 1 + 2 x 2 + 4× x 3 ≥ 4,

Rješenje:

Imamo početni problem minimizacije sa sistemom ograničenja u obliku nejednakosti, odnosno, par dualnih problema ima simetričnu formu 3. tipa, čiji matematički model u matričnom obliku ima oblik:

Originalni problem Dvostruki problem

F = C × X min F = B T × Y max

kod A × X ≥ B i A T × Y ≤ S T

X ≥ 0 Y ≥ 0

U originalnom problemu, matrica-red koeficijenata za varijable u funkciji cilja, matrica-kolona slobodnih termina i matrica koeficijenata za varijable u sistemu ograničenja imaju oblik

C = (1; 1; 1), B = 3, A = 6 4 5

Nađimo matrice dualnog problema

B T = (2; 3; 4) C T = 3 A T = 9 4 2

Dvostruki problem je formuliran kao:

Maksimizirajte ciljnu funkciju F = 2y 1 + 3y 2 + 4y 3

pod ograničenjima 3 × y 1 + 6 × y2+8 × y 3 ≤ 1,

9× y 1 + 4 × y2+2 × y 3 ≤ 1,

7× y 1 + 5 × y2+4 × y 3 ≤ 1,

y i ≥ 0 (i = 1, 2, 3)

ZADATAK 2.C. Rješavanje problema linearnog programiranja korištenjem simpleks tablica.

Opcija 7. Maksimizirajte funkciju cilja F = 2 x 1 - x 2 + 3 x 3 + 2 x 4

sa ograničenjima: 2 x 1 + 3 x 2 - x 3 + 2 x 4 ≤ 4,

x 1 - 2 x 2 + 5 x 3 - 3 x 4 ≥ 1,

4 x 1 + 10 x 2 +3 x 3 + x 4 ≤ 8.

Rješenje:

Dovedemo sistem ograničenja u kanonski oblik

2 x 1 + 3 x 2 – x 3 + 2 x 4 + z 1 = 4, (1)

x 1 - 2 x 2 + 5 x 3 - 3 x 4 - z 2 = 1, (2)

4 x 1 + 10 x 2 +3 x 3 + x 4 + z 3 = 8. (3)

Imamo sistem od 3 jednačine sa 7 nepoznatih. Odaberimo 3 varijable x 1 , z 1 , z 3 kao osnovne, x 2 , x 3 , x 4 , z 2 kao slobodne i izrazimo osnovne varijable kroz njih.

Iz (2) imamo x 1 = 1 + 2 x 2 - 5 x 3 + 3 x 4 + x 6

Zamijenimo u (1) i (3), dobićemo

x 1 - 2 x 2 + 5 x 3 - 3 x 4 - z 2 = 1,

z 1 + 7 x 2 - 11 x 3 + 8 x 4 + 2 z 2 = 2,

z 3 + 18 x 2 - 17 x 3 + 13 x 4 + 4 z 2 = 4,

F - 3 x 2 + 7 x 3 - 8 x 4 - 2 z 2 = 2.

Kreirajmo simpleks tablicu

I iteracija Tabela 1

Basic AC	Sloboda. AC
x 1	1	1	— 2	5	— 3	0	— 1	0		3/8
z 1	2	0	7	-11		1	2	0	1/ 4	1/8
z 3	4	0	18	-17	13	0	4	1	4/13	13/8
F	2	0	— 3	7	— 8	0	— 2	0		1

X 1 = (1; 0; 0; 0; 2; 0; 4) F 1 = 2.

II iteracija Tabela 2

x 1	14/8	1	5/8	7/8	0	3/8	-2/8	0	2	— 1
x 4	1/ 4	0	7/8	-11/8	1	1/8	2/8	0		11/7
z 3	6/8	0	53/8		0	-13/8	6/8	1	6/7	8/7
F	4	0	4	— 4	0	1	0	0		32/7

X 2 = (14/8; 0; 0; 1/4; 0; 0; 4) F 2 = 4.

III iteracija Tabela 3

x 1	1	1	— 6	0	0		-1	— 1		1/2
x 4	10/ 7	0	79/7	0	1	-17/7	10/7	11/7		11/7
x 3	6/7	0	53/7	1	0	-13/7	6/7	8/7		13/14
F	52/7	0	240/7	0	0	-45/7	24/7	32/7		45/14

X 3 = (1; 0; 6/7; 10/7; 0; 0; 0) F 3 = 52/7.

IV iteracija Tabela 4

z 1	1/ 2	1/2	— 3	0	0	1	-1/2	-1/2
x 4	37/ 14	17/14	56/14	0	1	0	3/14	5/14
x 3	25/14	13/14	28/14	1	0	0	-1/14	3/14
F	149/14	45/14	15	0	0	0	3/14	19/14

X 4 = (0; 0; 25/14; 37/14; 1/2; 0; 0) F 4 = 149/14.

Nema zadnje tabele u indeksnom redu negativni brojevi, odnosno u izrazu za ciljnu funkciju sve G i< 0. Имеем случай I, следовательно, последнее базисное решение является оптимальным.

Odgovor: F m ax = 149/14,

optimalno rješenje (0; 0; 25/14; 37/14; 1/2; 0; 0)

Opcija 8. Minimizirajte ciljnu funkciju F = 5 x 1 - x 3

pod ograničenjima: x 1 + x 2 + 2 x 3 - x 4 = 3,

x 2 + 2 x 4 =1,

Rješenje:

Broj varijabli je 4, rang matrice je 2, stoga je broj slobodnih varijabli r = 4 - 2 = 2, broj osnovnih varijabli je također 2. Uzmimo x 3, x 4 kao slobodne varijable, izrazimo osnovne varijable x 1, x 2 u terminima slobodnih i Hajde da svedemo sistem na jediničnu osnovu:

x 2 = 1 - 2 x 4,

x 1 = 3 - x 2 - 2 x 3 + x 4 = 3 - 1 + 2 x 4 - 2 x 3 + x 4 = 2 - 2 x 3 + 3 x 4

F = 5 x 1 - x 3 = 5 (2 - 2 x 3 + 3 x 4) - x 3 = 10 - 10 x 3 + 15 x 4 - x 3 = 10 - 11 x 3 + 15 x 4

Zapišimo sistem jednačina i ciljnu funkciju u obliku pogodnom za simpleks tablicu, to jest, x 2 + 2 x 4 = 1,

x 1 +2 x 3 - 3 x 4 = 2

Ž + 11 x 3 - 15 x 4 = 10

Hajde da napravimo sto

I iteracija Tabela 1

Basic AC	Sloboda. AC
X 1	2	1	0		— 3		1/2
X 2	1	0	1	0	2
F	10	0	0	11	— 15		— 11/2

X 1 = (2; 1; 0; 0) F 1 = 10.

II iteracija Tabela 2

X 3	1	1/2	0	1	-3/2		3/4
X 2	1	0	1	0			1/2
F	— 1	— 11/2	0	0	3/2		— 3/4

X 2 = (0; 1; 1; 0) F 2 = -1.

III iteracija Tabela 3

X 3	7/4	1/2	3/4	1	0
X 4	1/2	0	1/2	0	1
F	— 7/4	— 11/2	— 3/4	0	0

X 3 = (0; 0; 7/4; 1/2) F 3 = -7/4.

U indeksnom redu poslednje tabele nema pozitivnih brojeva, odnosno u izrazu za ciljnu funkciju sve G i > 0. Imamo slučaj I, dakle, poslednje osnovno rešenje je optimalno.

Odgovor: F min = -7/4, optimalno rješenje (0; 0; 7/4; 1/2)

********************

Opcija 10. Minimizirati ciljnu funkciju F = x 1 + x 2,

pod ograničenjima: x 1 –2 x 3 + x 4 = 2,

x 2 – x 3 + 2 x 4 = 1,

Rješenje:

Broj varijabli je 5, rang matrice je 3, stoga je broj slobodnih varijabli r = 6-3 = 2. Uzmimo x 3 i x 4 kao slobodne varijable, a x 1 , x 2 , x 5 kao osnovne. Sve jednačine sistema su već svedene na jediničnu osnovu (osnovne varijable su izražene kao slobodne), ali su napisane u obliku koji nije pogodan za korišćenje simpleks tabela. Zapišimo sistem jednačina u obliku

x 1 - 2 x 3 + x 4 = 2

x 2 - x 3 +2 x 4 = 1

x 5 + x 3 – x 4 . = 5

Funkciju cilja izražavamo u terminima slobodnih varijabli i zapisujemo je u obliku F - 3 x 3 +3 x 4 = 3

Hajde da napravimo sto

I iteracija Tabela 1

Basic AC	Sloboda. AC
x 1	2	1	0	-2	1	0	2	-1/2
x 2	1	0	1	-1		0	1/2	1/2
x 5	5	0	0	1	-1	1		1/2
F	3	0	0	-3	3	0		-3/2

X 1 = (2; 3; 0; 0; 5) F 1 = 3.

tabela 2

x 1	3/2	1	-1/2	-3/2	0	0
x 4	1/2	0	1/2	-1/2	1	0
x 5	11/2	0	1/2	1/2	0	1
F	3/2	0	-3/2	-3/2	0	0

X 2 = (3/2; 0; 0; 1/2; 11/2) F 2 = 3/2.

U indeksnom redu zadnje tabele nema pozitivnih brojeva, odnosno u izrazu za ciljnu funkciju svi Gi > 0. Imamo slučaj 1, dakle, poslednje osnovno rešenje je optimalno.

Odgovor: F min = 3/2, optimalno rješenje (3/2; 0; 0; 1/2; 11/2).

Federalna agencija za obrazovanje

Državni budžet obrazovne ustanove

viši stručno obrazovanje

"Omski državni tehnički univerzitet"

RAČUNSKI I GRAFIČKI RAD

po disciplini"TEORIJA OPTIMALNOG UPRAVLJANJA »

na temu"METODE OPTIMIZACIJE I ISTRAŽIVANJE OPERACIJA »

opcija 7

Završeno:

dopisni student

Grupa 4. godine ZA-419

Puno ime: Kuzhelev S. A.

Provjereno:

Devyaterikova M. V.

Omsk – 2012
^

Zadatak 1. Grafička metoda za rješavanje problema linearnog programiranja.

7) 7x 1 + 6x 2 → maks 20x 1 + 6x 2 ≤ 15 16x 1 − 2x 2 ≤ 18 8x 1 + 4x 2 ≤ 20 13x 1 + 3x 2 ≤ 4 x 1 , x 2 ≥ 0.

Korak 1: Izgradnja izvodljivog regiona

Uslovi nenegativnosti varijabli i kvadrata ograničavaju raspon njihovih dozvoljenih vrijednosti na prvi kvadrant. Svako od preostale četiri ograničenja nejednakosti modela odgovara određenoj poluravni. Presek ovih poluravnina sa prvim kvadrantom formira skup izvodljivih rešenja problema.

Prvo ograničenje modela ima oblik . Zamenivši u njemu znak ≤ znakom =, dobijamo jednačinu . Na sl. 1.1 definira pravu liniju (1), koja dijeli ravan na dvije poluravni, u u ovom slučaju iznad i ispod linije. Odabrati koji od njih zadovoljava nejednakost , zamijenite u njega koordinate bilo koje tačke koja ne leži na datoj pravoj (na primjer, ishodište X 1 = 0, X 2 = 0). Pošto smo dobili tačan izraz (20 0 + 6 0 = 0 ≤15), tada poluravnina koja sadrži početak koordinata (označena strelicom) zadovoljava nejednakost. Inače, još jedan poluravan.

Na sličan način postupamo s preostalim ograničenjima problema. Nastaje presek svih konstruisanih poluravnina sa prvim kvadrantom A B C D(vidi sliku 1). Ovo je izvodljivo područje problema.

Korak 2. Crtanje linije nivoa Linija nivoa Funkcija cilja je skup tačaka u ravni u kojima funkcija cilja poprima konstantnu vrijednost. Takav skup je dat jednadžbom f ( x) = konst. Stavimo npr. konst = 0 i nacrtajte liniju na nivou f ( x) = 0, tj. u našem slučaju prava linija 7 x 1 + 6x 2 = 0.

Ova linija prolazi kroz ishodište i okomita je na vektor. Ovaj vektor je gradijent funkcije cilja u tački (0,0). Gradijent funkcije je vektor vrijednosti parcijalnih izvoda date funkcije u točki o kojoj je riječ. U slučaju LP problema, parcijalni izvod funkcije cilja jednaki su koeficijentima Cja, j = 1 , ..., n.

Gradijent pokazuje smjer najbržeg rasta funkcije. Pomicanje linije razine funkcije cilja f ( x) = konst. okomito na smjer gradijenta, nalazimo posljednju tačku u kojoj se on siječe sa regijom. U našem slučaju, ovo je tačka D, koja će biti maksimalna tačka funkcije cilja (vidi sliku 2)

Leži na presjeku linija (2) i (3) (vidi sliku 1) i specificira optimalno rješenje.

^ Imajte na umu da ako želite pronaći minimalnu vrijednost funkcije cilja, linija nivoa se pomiče u smjeru suprotnom od smjera gradijenta.

^ Korak 3. Određivanje koordinata maksimalne (minimalne) tačke i optimalne vrijednosti funkcije cilja

Da biste pronašli koordinate tačke C, potrebno je riješiti sistem koji se sastoji od jednadžbi koje odgovaraju pravim linijama (u ovom slučaju jednačine 2 i 3):

16x 1 − 2x 2 ≤ 18

8x 1 + 4x 2 ≤ 20

Dobijamo optimalno rješenje = 1,33.

^ Optimalna vrijednost ciljna funkcija f * = f (X*) = 7 * 0 + 6 * 1,33 = 7,8

KONTROLNI RAD NA DISCIPLINI:

“METODE OPTIMALNIH REŠENJA”

Opcija br. 8

1. Riješite grafički problem linearnog programiranja. Pronađite maksimum i minimum funkcije sa datim ograničenjima:

,

.

Rješenje

Potrebno je pronaći minimalnu vrijednost funkcije cilja i maksimum, pod sistemom ograničenja:

9x 1 +3x 2 ≥30, (1)

X 1 +x 2 ≤4, (2)

x 1 +x 2 ≤8, (3)

Konstruirajmo područje izvodljivih rješenja, tj. Rešimo sistem nejednačina grafički. Da bismo to učinili, konstruiramo svaku pravu liniju i definiramo poluravnine definirane nejednačinama (poluravnine su označene prostim brojem).

Presek poluravni će biti oblast čije koordinate tačaka zadovoljavaju nejednakosti sistema ograničenja problema. Označimo granice površine poligona rješenja.

Konstruirajmo pravu liniju koja odgovara vrijednosti funkcije F = 0: F = 2x 1 +3x 2 = 0. Vektor gradijenta, sastavljen od koeficijenata funkcije cilja, pokazuje smjer minimizacije F(X). Početak vektora je tačka (0; 0), kraj je tačka (2; 3). Pomeraćemo ovu pravu liniju na paralelan način. Budući da nas zanima minimalno rješenje, pomičemo pravu liniju sve dok ona ne dodirne označenu oblast. Na grafikonu je ova prava linija označena isprekidanom linijom.

Pravo
siječe područje u tački C. Pošto je tačka C dobijena kao rezultat preseka pravih (4) i (1), njene koordinate zadovoljavaju jednačine ovih pravih:
.

Nakon što smo riješili sistem jednačina, dobijamo: x 1 = 3,3333, x 2 = 0.

Kako možemo pronaći minimalnu vrijednost ciljne funkcije: .

Razmotrimo ciljnu funkciju problema.

Konstruirajmo pravu liniju koja odgovara vrijednosti funkcije F = 0: F = 2x 1 +3x 2 = 0. Vektor gradijenta, sastavljen od koeficijenata funkcije cilja, pokazuje smjer maksimizacije F(X). Početak vektora je tačka (0; 0), kraj je tačka (2; 3). Pomeraćemo ovu pravu liniju na paralelan način. Budući da nas zanima maksimalno rješenje, pomičemo pravu liniju do posljednjeg dodira označenog područja. Na grafikonu je ova prava linija označena isprekidanom linijom.

Pravo
seče područje u tački B. Pošto je tačka B dobijena kao rezultat preseka pravih (2) i (3), njene koordinate zadovoljavaju jednačine ovih pravih:

.

Kako možemo pronaći maksimalnu vrijednost ciljne funkcije: .

odgovor:
I
.

2 . Riješite problem linearnog programiranja korištenjem simpleks metode:

.

Rješenje

Rešimo problem direktnog linearnog programiranja upotrebom simpleks metode, koristeći simpleks tablicu.

Odredimo minimalnu vrijednost funkcije cilja
pod sledećim uslovima-ograničenjima:
.

Da bismo konstruirali prvi referentni plan, sistem nejednačina svodimo na sistem jednačina uvođenjem dodatnih varijabli.

U 1. nejednakosti značenja (≥) uvodimo osnovnu varijablu x 3 sa znakom minus. U 2. nejednakosti značenja (≤) uvodimo osnovnu varijablu x 4 . U 3. nejednakosti značenja (≤) uvodimo osnovnu varijablu x 5 .

Hajde da uvedemo veštačke varijable : u 1. jednakosti uvodimo varijablu x 6 ;

Da bismo problem postavili na minimum, zapisujemo funkciju cilja na sljedeći način: .

Za korištenje umjetnih varijabli uvedenih u funkciju cilja, izriče se takozvana kazna M, vrlo veliki pozitivan broj koji se obično ne specificira.

Rezultirajuća baza naziva se umjetna, a metoda rješenja naziva se metoda umjetne baze.

Štoviše, umjetne varijable nisu povezane sa sadržajem problema, ali omogućavaju konstruiranje početne točke, a proces optimizacije prisiljava ove varijable da uzmu nulte vrijednosti i osiguravaju prihvatljivost optimalnog rješenja.

Iz jednačina izražavamo umjetne varijable: x 6 = 4-x 1 -x 2 +x 3, koje zamjenjujemo u ciljnu funkciju: ili.

Matrica koeficijenata
ovaj sistem jednačina ima oblik:
.

Rešimo sistem jednačina za osnovne varijable: x 6 , x 4 , x 5.

Uz pretpostavku da su slobodne varijable jednake 0, dobijamo prvu referentni plan:

X1 = (0,0,0,2,10,4)

Osnovno rješenje se naziva dopuštenim ako nije negativno.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6
x 4
x 5

Trenutni referentni plan nije optimalan jer u indeksnoj liniji postoje pozitivni koeficijenti. Kao vodeći stupac izabraćemo kolonu koja odgovara varijabli x 2, jer je to najveći koeficijent. Izračunajmo vrijednosti D i a od njih biramo najmanji: min(4:1, 2:2, 10:2) = 1.

Dakle, 2. red je vodeći.

Element za razlučivanje jednak je (2) i nalazi se na presjeku vodeće kolone i vodećeg reda.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6
x 4
x 5

Formiramo sljedeći dio tabele simpleksa. Umjesto varijable x 4, plan 1 će uključivati ​​varijablu x 2.

Red koji odgovara varijabli x 2 u planu 1 dobija se dijeljenjem svih elemenata reda x 4 plana 0 sa elementom za razrješenje RE = 2. Umjesto elementa za rješavanje dobijamo 1. U preostale ćelije kolone x 2 upisujemo nule.

Tako se u novom planu 1 popunjavaju red x 2 i kolona x 2. Svi ostali elementi novog plana 1, uključujući elemente indeksnog reda, određeni su pravilom pravokutnika.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6
x 2
x 5
		1 1/2 +1 1/2 M

Trenutni referentni plan nije optimalan jer u indeksnom redu postoje pozitivni koeficijenti. Kao vodeći stupac izabraćemo kolonu koja odgovara varijabli x 1, jer je to najveći koeficijent. Izračunajmo vrijednosti D i po redu kao količnik dijeljenja: a od njih biramo najmanji: min (3: 1 1 / 2, -, 8: 2) = 2.

Dakle, 1. red je vodeći.

Element za razlučivanje jednak je (1 1/2) i nalazi se na sjecištu vodeće kolone i vodećeg reda.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6		1 1 / 2
x 2
x 5
		-1 1 / 2 +1 1 / 2 M

Formiramo sljedeći dio tabele simpleksa. Umjesto varijable x 6, plan 2 će uključivati ​​varijablu x 1.

Dobijamo novu simpleks tabelu:

		x 1	x 2	x 3	x 4	x 5	x 6
x 1
x 2
x 5

Među vrijednostima niza indeksa nema pozitivnih vrijednosti. Stoga ova tabela određuje optimalni plan za problem.

Konačna verzija simpleks tablice:

		x 1	x 2	x 3	x 4	x 5	x 6
x 1
x 2
x 5

Pošto u optimalnom rješenju nema umjetnih varijabli (jednake su nuli), ovo rješenje je dopušteno.

Optimalni plan se može napisati na sljedeći način: x 1 = 2, x 2 = 2:.

Odgovori:
,
.

3. Kompanija Tri debela isporučuje mesne konzerve iz tri skladišta u različitim delovima grada u tri prodavnice. Zalihe konzervirane hrane dostupne u skladištima, kao i količine narudžbi iz trgovine i cijene isporuke (u konvencionalnim novčanim jedinicama) prikazane su u transportnoj tabeli.

Pronađite plan prevoza koji obezbeđuje najniže novčane troškove (izvršite početni plan transporta metodom „sjeverozapadnog ugla“).

Rješenje

Provjerimo neophodan i dovoljan uslov za rješivost problema:

= 300 + 300 + 200 = 800 .

= 250 + 400 + 150 = 800.

Uslov ravnoteže je ispunjen. Isporučuje jednake potrebe. Stoga je model transportnog problema zatvoren.

Unesimo početne podatke u tabelu distribucije.

Potrebe

Koristeći metodu sjeverozapadnog ugla, napravićemo prvi referentni plan transportnog problema.

Plan se počinje popunjavati iz gornjeg lijevog ugla.

Traženi element je 4. Za ovaj element zalihe su 300, zahtjevi su 250. Pošto je minimum 250, oduzimamo ga: .

			300 - 250 = 50
250 - 250 = 0

Traženi element je jednak 2. Za ovaj element zalihe su 50, zahtjevi su 400. Pošto je minimum 50, oduzimamo ga: .

			50 - 50 = 0
	400 - 50 = 350

Traženi element je 5. Za ovaj element zalihe su 300, zahtjevi su 350. Pošto je minimum 300, oduzimamo ga:

			300 - 300 = 0
	350 - 300 = 50

Element koji tražite je 3. Za ovaj element zalihe su 200, zahtjevi su 50. Pošto je minimum 50, oduzimamo ga:

			200 - 50 = 150
	50 - 50 = 0

Traženi element je 6. Za ovaj element zalihe su 150, zahtjevi su 150. Pošto je minimum 150, oduzimamo ga:

			150 - 150 = 0
		150 - 150 = 0

Potrebe

Uvod

Sadašnji stupanj ljudskog razvoja odlikuje se činjenicom da doba energije zamjenjuje doba informatike. Intenzivno se uvode nove tehnologije u sve sfere ljudskog djelovanja. Postoji realan problem tranzicije u informatičko društvo, kojem razvoj obrazovanja treba postati prioritet. Struktura znanja u društvu se također mijenja. Sve važnije za praktičan život stiču temeljna znanja koja doprinose kreativnom razvoju pojedinca. Važna je i konstruktivnost stečenog znanja i sposobnost da se ono strukturira u skladu sa ciljem. Na osnovu znanja formiraju se novi informacionih resursa društvo. Formiranje i sticanje novih znanja treba da se zasniva na strogoj metodologiji sistemskog pristupa, u okviru koje modelski pristup zauzima posebno mesto. Mogućnosti modelskog pristupa su izuzetno raznolike, kako u pogledu formalnih modela koji se koriste, tako iu pogledu metoda implementacije metoda modeliranja. Fizičko modeliranje omogućava da se dobiju pouzdani rezultati za prilično jednostavne sisteme.

Trenutno je nemoguće imenovati oblast ljudske aktivnosti u kojoj se metode modeliranja ne bi koristile u ovom ili onom stepenu. Ovo se posebno odnosi na oblast upravljanja razni sistemi, gdje su glavni procesi donošenje odluka na osnovu primljenih informacija.

1. Izjava o problemu

minimalna funkcija cilja

Riješiti zadatak pronalaženja minimuma ciljne funkcije za sistem ograničenja specificiranih poligonom rješenja u skladu sa opcijom br. 16 zadatka. Poligon rješenja prikazan je na slici 1:

Slika 1 - Poligon rješenja problema

Sistem ograničenja i ciljna funkcija problema su predstavljeni u nastavku:

Problem je potrebno riješiti sljedećim metodama:

Grafička metoda rješavanja LP problema;

Algebarska metoda za rješavanje LP problema;

Simpleksna metoda za rješavanje LP problema;

Metoda za pronalaženje prihvatljivog rješenja za probleme LP;

Rješenje dvojnog LP problema;

Metoda grananja i granice za rješavanje cjelobrojnih LP problema;

Gomorijeva metoda za rješavanje cjelobrojnih LP problema;

Balazsova metoda za rješavanje Bulovih LP problema.

Uporedite rezultate rješenja različite metode izvući odgovarajuće zaključke iz rada.

2. Grafičko rješenje problema linearnog programiranja

Grafička metoda za rješavanje problema linearnog programiranja koristi se u slučajevima kada broj nepoznatih ne prelazi tri. Pogodan je za kvalitativno istraživanje svojstava rješenja i koristi se u kombinaciji s drugim metodama (algebarskim, granskim i vezanim itd.). Ideja metode je zasnovana na grafičkom rješenju sistema linearnih nejednačina.

Rice. 2 Grafičko rješenje LP problema

Minimalni poen

Jednadžba prave koja prolazi kroz dvije tačke A1 i A2:

AB: (0;1); (3;3)

VS: (3;3); (4;1)

CD: (4;1); (3;0)

EA: (1;0); (0;1)

CF: (0;1); (5;2)

uz ograničenja:

Rješavanje problema linearnog programiranja korištenjem algebarske simpleks metode

Primjena algebarske metode za rješavanje problema zahtijeva generalizaciju reprezentacije LP problema. Originalni sistem ograničenja, specificiran u obliku nejednakosti, pretvara se u standardnu ​​notaciju kada su ograničenja specificirana u obliku jednakosti. Transformacija sistema ograničenja na standardni pogled uključuje sljedeće korake:

Transformirajte nejednačine tako da na lijevoj strani budu varijable i slobodni članovi, a na desnoj 0, tj. to lijeva strana bio veći ili jednak nuli;

Uvesti dodatne varijable čiji je broj jednak broju nejednakosti u sistemu ograničenja;

Uvođenjem dodatnih ograničenja na nenegativnost dodanih varijabli zamijenite znakove nejednakosti strogim predznacima jednakosti.

Prilikom rješavanja LP problema algebarskom metodom dodaje se uvjet: ciljna funkcija mora težiti minimumu. Ako ovo stanje nije zadovoljan, potrebno je u skladu s tim transformirati ciljnu funkciju (pomnožiti sa -1) i riješiti problem minimizacije. Nakon što se pronađe rješenje, zamijenite vrijednosti varijabli u originalnu funkciju i izračunajte njenu vrijednost.

Rješenje problema algebarskom metodom smatra se optimalnim kada su vrijednosti svih osnovnih varijabli nenegativne, a koeficijenti slobodnih varijabli u jednadžbi ciljne funkcije također nisu negativni. Ukoliko ovi uslovi nisu ispunjeni, potrebno je transformisati sistem nejednakosti, izražavajući neke varijable u terminima drugih (promjenom slobodnih i osnovnih varijabli) kako bi se postiglo ispunjenje navedenih ograničenja. Vrijednost svih slobodnih varijabli smatra se jednakom nuli.

Algebarska metoda za rješavanje problema linearnog programiranja je jedna od najčešćih efikasne metode prilikom ručnog rješavanja malih problema jer ne zahtijeva veliki broj aritmetičkih proračuna. Mašinska implementacija ove metode je složenija nego, na primjer, za simpleks metodu, jer Algoritam rješenja korištenjem algebarske metode je u određenoj mjeri heuristički i djelotvornost rješenja u velikoj mjeri ovisi o ličnom iskustvu.

Slobodne varijable

St. lane - dodatno komplet

Uslovi nenegativnosti su ispunjeni, stoga je pronađeno optimalno rješenje.

3. Rješavanje problema linearnog programiranja korištenjem simpleks tablice

Rješenje: Dovedemo problem u standardni oblik za rješenje koristeći simpleks tablicu.

Svedemo sve jednačine sistema na oblik:

Izrađujemo simpleks tabelu:

U gornji ugao svake ćelije tabele upisujemo koeficijente iz sistema jednačina;

Odabiremo maksimalni pozitivni element u redu F, osim što će to biti opći stupac;

Da bismo pronašli opšti element, gradimo odnos za sve pozitivne. 3/3; 9/1;- minimalni odnos u redu x3. Stoga - opći niz i =3 - opći element.

Nalazimo =1/=1/3. Donosimo ga u donji ugao ćelije gdje se nalazi opći element;

U sve prazne donje kutove opće linije unosimo proizvod vrijednosti u gornjem uglu ćelije po;

Odaberite gornje uglove opće linije;

U sve donje kutove opće kolone unosimo proizvod vrijednosti u gornji kut sa - i odabiremo rezultirajuće vrijednosti;

Preostale ćelije tabele se popunjavaju kao produkti odgovarajućih odabranih elemenata;

Zatim pravimo novu tabelu u kojoj se zamenjuju oznake ćelija elemenata opšte kolone i reda (x2 i x3);

Vrijednosti koje su prethodno bile u donjem kutu upisane su u gornji ugao bivšeg općeg reda i stupca;

Zbir vrijednosti gornjih i donjih uglova ovih ćelija u prethodnoj tabeli upisan je u gornjem uglu preostalih ćelija

4. Rješavanje problema linearnog programiranja pronalaženjem prihvatljivog rješenja

Neka je dat sistem linearnih algebarskih jednadžbi:

Možemo pretpostaviti da je sve, inače odgovarajuću jednačinu množimo sa -1.

Uvodimo pomoćne varijable:

Uvodimo i pomoćnu funkciju

Sistem ćemo minimizirati pod ograničenjima (2) i uslovima.

PRAVILO ZA PRONALAŽENJE DOZVOLJENOG RJEŠENJA: Da bismo pronašli prihvatljivo rješenje za sistem (1), minimiziramo oblik (3) pod ograničenjima (2), uzimamo xj kao slobodne nepoznanice, a uzimamo xj kao osnovne.

Prilikom rješavanja problema simpleks metodom mogu se pojaviti dva slučaja:

min f=0, tada svi i moraju biti jednaki nuli. I rezultirajuće vrijednosti xj će predstavljati prihvatljivo rješenje za sistem (1).

min f>0, tj. originalni sistem nema izvodljivo rješenje.

Izvorni sistem:

Koristi se uslov zadatka iz prethodne teme.

Hajde da uvedemo dodatne varijable:

Pronađeno je prihvatljivo rješenje originalnog problema: x1 = 3, x2 = 3, F = -12. Na osnovu dobijenog izvodljivog rješenja naći ćemo optimalno rješenje originalnog problema primenom simpleks metode. Da bismo to učinili, napravit ćemo novu simpleks tablicu iz gore dobivene tablice, uklanjajući red i red s ciljnom funkcijom pomoćnog problema:

Analizirajući konstruiranu simpleks tablicu, vidimo da je optimalno rješenje za originalni problem već pronađeno (elementi u redu koji odgovaraju funkciji cilja su negativni). Dakle, izvodljivo rješenje pronađeno pri rješavanju pomoćnog problema poklapa se s optimalnim rješenjem izvornog problema:

6. Problem dvostrukog linearnog programiranja

Originalni sistem ograničenja i ciljna funkcija problema prikazani su na donjoj slici.

uz ograničenja:

Rješenje: Dovedemo sistem ograničenja u standardni oblik:

Problem dvojan ovom će imati oblik:

Rješenje dualnog problema bit će izvedeno jednostavnom simpleks metodom.

Transformirajmo ciljnu funkciju tako da problem minimizacije bude riješen i napišemo sistem ograničenja u standardnom obliku za rješavanje simpleks metodom.

y6 = 1 - (-2 y1 + 2y2 +y3 + y4+ y5)

y7 = 5 - (-3y1 - y2 + y3 + y4)

F = 0 - (3y1 + 9y2 + 3y3 + y4) ??min

Konstruirajmo početnu simpleks tablicu za rješavanje dualnog LP problema.

Drugi korak simpleks metode

Dakle, u trećem koraku simpleks metode pronađeno je optimalno rješenje problema minimizacije sa sljedećim rezultatima: y2 = -7 /8, y1 = -11/8, F = 12. Da bi se pronašla vrijednost ciljnu funkciju dualnog problema, zamjenjujemo pronađene vrijednosti osnovnih i slobodnih varijabli u funkciju maksimizacije:

Fmax = - Fmin = 3*(-11/8) + 9(-7/8) + 3*0 + 0 = -12

Budući da se vrijednost ciljne funkcije direktnog i dualnog problema poklapa, rješenje direktnog problema je pronađeno i jednako je 12.

Fmin = Fmax = -12

7. Rješavanje problema cjelobrojnog linearnog programiranja korištenjem metode grane i granice

Transformirajmo originalni problem na takav način da uvjet cijelog broja nije zadovoljen kada se rješava konvencionalnim metodama.

Početni poligon rješenja problema cjelobrojnog programiranja.

Za transformirani poligon rješenja konstruiramo novi sistem ograničenja.

Zapišimo sistem ograničenja u obliku jednakosti koje treba riješiti algebarskom metodom.

Kao rezultat rješenja pronađen je optimalni plan za zadatak: x1 = 9/4, x2 = 5/2, F = -41/4. Ovo rješenje ne ispunjava cjelobrojni uvjet postavljen u problemu. Podijelimo originalni poligon rješenja na dvije oblasti, isključujući područje 3 iz njega

Modificiran poligon rješenja problema

Kreirajmo nove sisteme ograničenja za rezultujuće površine poligona rješenja. Lijevo područje je četverougao (trapez). Sistem ograničenja za lijevu oblast poligona rješenja prikazan je u nastavku.

Sistem ograničenja za lijevu oblast

Desno područje predstavlja tačku C.

Sistem ograničenja za region prave odluke je predstavljen u nastavku.

Novi sistemi ograničenja predstavljaju dva pomoćna problema koja se moraju rješavati nezavisno jedan od drugog. Hajde da riješimo problem cjelobrojnog programiranja za lijevo područje poligona rješenja.

Kao rezultat rješenja pronađen je optimalni plan za zadatak: x1 = 3, x2 = 3, F = -12. Ovaj plan zadovoljava uvjet da su varijable u problemu cjelobrojne i može se prihvatiti kao optimalni referentni plan za originalni cjelobrojni problem linearnog programiranja. Nema smisla rješavati za pravi region rješenja. Slika ispod prikazuje napredak rješavanja cjelobrojnog linearnog programskog problema u obliku stabla.

Napredak rješavanja problema cjelobrojnog linearnog programiranja korištenjem Gomorijeve metode.

U mnogim praktičnim primjenama, problem cjelobrojnog programiranja u kojem je dat sistem linearnih nejednakosti i linearni oblik je od velikog interesa

Potrebno je pronaći cjelobrojno rješenje sistema (1) koje minimizira ciljnu funkciju F, a svi koeficijenti su cijeli brojevi.

Gomori je predložio jednu od metoda za rješavanje problema cjelobrojnog programiranja. Ideja metode je korištenje metoda kontinuiranog linearnog programiranja, posebno simpleks metode.

1) Primenom simpleks metode određuje se rešenje zadatka (1), (2), za koje se ukida zahtev za celobrojnim rešenjem; ako se ispostavi da je rješenje cijeli broj, tada će se pronaći i željeno rješenje cjelobrojnog problema;

2) U suprotnom, ako neka koordinata nije cijeli broj, rezultirajuće rješenje problema se provjerava na mogućnost postojanja cjelobrojnog rješenja (prisustvo cjelobrojnih tačaka u dopuštenom poliedru):

ako se u bilo kojem redu s razlomkom slobodnog člana svi ostali koeficijenti pokažu kao cijeli brojevi, tada u dopuštenom poliedru nema cijelih brojeva ili tačaka i problem cjelobrojnog programiranja nema rješenja;

U suprotnom, uvodi se dodatno linearno ograničenje, koje odsiječe dio dopuštenog poliedra koji nije obećavajući za pronalaženje rješenja problema cjelobrojnog programiranja;

3) Da biste konstruirali dodatno linearno ograničenje, odaberite l-ti red sa slobodnim razlomkom i napišite dodatno ograničenje

gdje su i razlomci koeficijenata i slobodni

član. Hajde da uvedemo pomoćnu varijablu u ograničenje (3):

Odredimo koeficijente i uključimo ih u ograničenje (4):

gdje su i najbliži cijeli brojevi odozdo za i respektivno.

Gomori je dokazao da konačan broj sličnih koraka dovodi do problema linearnog programiranja čije je rješenje cjelobrojno i stoga željeno.

Rješenje: Dovedemo sistem linearnih ograničenja i ciljnu funkciju u kanonski oblik:

Odredimo optimalno rješenje za sistem linearnih ograničenja, privremeno odbacujući cijeli broj. Za to koristimo simpleks metodu. U nastavku, sekvencijalno u tabelama, prikazano je originalno rješenje problema, a date su i transformacije originalne tablice kako bi se dobilo optimalno rješenje problema:

Rješavanje Booleovih LP problema korištenjem Balazsove metode.

Kreirajte vlastitu verziju za cjelobrojni problem linearnog programiranja s Booleovim varijablama, uzimajući u obzir sljedeća pravila: problem koristi najmanje 5 varijabli, najmanje 4 ograničenja, koeficijenti ograničenja i ciljne funkcije biraju se proizvoljno, ali u takvom način na koji je sistem ograničenja kompatibilan. Zadatak je riješiti LCLP sa Booleovim varijablama koristeći Balazs algoritam i odrediti smanjenje složenosti proračuna u odnosu na rješavanje problema korištenjem metode iscrpnog pretraživanja.

Izvršenje ograničenja

F vrijednost

Ograničenje filtriranja:

Određivanje smanjenja računskog napora

Rješenje problema korištenjem metode iscrpnog pretraživanja je 6*25=192 izračunatih izraza. Rješenje problema primjenom Balazs metode je 3*6+(25-3)=47 izračunatih izraza. Ukupno smanjenje složenosti proračuna u odnosu na rješavanje problema korištenjem metode iscrpnog pretraživanja je:

Zaključak

Proces projektovanja informacionih sistema koji implementiraju novu informatičku tehnologiju stalno se unapređuje. Fokus sistemskih inženjera je sve više na složenim sistemima, što otežava upotrebu fizičkih modela i povećava važnost matematičkih modela i mašinske simulacije sistema. Simulacija mašina je postala efikasan alat za proučavanje i projektovanje složenih sistema. Relevantnost matematičkih modela kontinuirano raste zbog njihove fleksibilnosti, adekvatnosti realnim procesima i niske cijene implementacije na bazi savremenih računara. Sve više mogućnosti pruža se korisniku, odnosno specijalistu za modeliranje sistema pomoću računarske tehnologije. Upotreba modeliranja je posebno efikasna u ranim fazama projektovanja automatizovanih sistema, kada je cena pogrešnih odluka najvažnija.

Savremeni računarski alati su omogućili da se značajno poveća složenost modela koji se koriste u proučavanju sistema, postalo je moguće graditi kombinovane, analitičke i simulacione modele koji uzimaju u obzir čitav niz faktora koji se javljaju u realnim sistemima, tj. , korištenje modela koji su adekvatniji fenomenima koji se proučavaju.

književnost:

1. Lyashchenko I.N. Linearno i nelinearno programiranje / I.N.Lyashchenko, E.A.Karagodova, N.V.Shor. - K.: “Viša škola”, 1975, 372 str.

2. Metodičko uputstvo za izvođenje kursa iz discipline „Primenjena matematika“ za studente specijalnosti „Računarski sistemi i mreže“ redovnog i vanrednog oblika studija / Sastavili: I.A. Balakireva, A.V. Izdavačka kuća SevNTU, 2003. - 15 str.

3. Smjernice za izučavanje discipline “Primijenjena matematika”, odjeljak “Metode globalnog pretraživanja i jednodimenzionalne minimizacije” / Kom. A.V. Skatkov, I.A. Balakireva, L.A. Litvinova - Sevastopolj: Izdavačka kuća SevGTU, 2000. - 31 str.

4. Smjernice za izučavanje discipline “Primijenjena matematika” za studente specijalnosti “Računarski sistemi i mreže” Odjeljak “Rješavanje problema cjelobrojnog linearnog programiranja” za redovno i vanredno obrazovanje / Sastavio: I.A. Balakireva, A.V : Izdavačka kuća SevNTU, 2000. - 13 str.

5. Akulich I.L. Matematičko programiranje u primjerima i problemima:

6. Udžbenik dodatak za studente ekonomije. specijalista. univerziteti.-M.: Viši. škola, 1986.- 319 str., ilustr.

7. Andronov S.A. Metode optimalnog projektovanja: Tekst predavanja / SPbSUAP. Sankt Peterburg, 2001. 169 str.: ilustr.

Slični dokumenti

Algoritam za rješavanje problema linearnog programiranja primjenom simpleks metode. Izgradnja matematičkog modela problema linearnog programiranja. Rješavanje problema linearnog programiranja u Excelu. Pronalaženje profita i optimalnog plana proizvodnje.

kurs, dodan 21.03.2012


Grafičko rješavanje problema. Izrada matematičkog modela. Određivanje maksimalne vrijednosti funkcije cilja. Rješenje simpleks metodom sa umjetnom osnovom problema kanonskog linearnog programiranja. Provjera optimalnosti rješenja.

test, dodano 05.04.2016


Teorijske osnove linearnog programiranja. Problemi linearnog programiranja, metode rješenja. Analiza optimalnog rješenja. Rješenje problema jednoindeksnog linearnog programiranja. Izjava o problemu i unos podataka. Konstrukcija modela i faze rješenja.

kurs, dodan 09.12.2008


Konstrukcija matematičkog modela. Izbor, opravdanje i opis metode za rješavanje problema direktnog linearnog programiranja primjenom simpleks metode, korištenjem simpleks tablice. Formulacija i rješenje dvojnog problema. Analiza osjetljivosti modela.

kurs, dodato 31.10.2014


Izrada matematičkog modela u cilju postizanja maksimalnog profita za preduzeće, grafičko rešenje problema. Rješavanje problema korištenjem SOLVER dodatka. Analiza promjena u rezervama resursa. Određivanje granica za promjenu koeficijenata funkcije cilja.

kurs, dodan 17.12.2014


Matematičko programiranje. Linearno programiranje. Problemi linearnog programiranja. Grafička metoda za rješavanje problema linearnog programiranja. Ekonomska formulacija problema linearnog programiranja. Konstrukcija matematičkog modela.

kurs, dodan 13.10.2008


Rješavanje problema linearnog programiranja grafičkom metodom, provjera u MS Excel-u. Analiza unutrašnje strukture rješavanja problema u programu. Optimizacija plana proizvodnje. Rješavanje problema simpleks metodom. Višekanalni sistem čekanja.

test, dodano 02.05.2012


Rješavanje problema linearnog programiranja simpleks metodom: izrada problema, konstrukcija ekonomskog i matematičkog modela. Rješavanje transportnog problema metodom potencijala: izrada početnog referentnog plana, određivanje njegove optimalne vrijednosti.

test, dodano 04.11.2012


Izjava o problemu nelinearnog programiranja. Određivanje stacionarnih tačaka i njihovog tipa. Konstrukcija linija nivoa, trodimenzionalni graf funkcije cilja i ograničenja. Grafičko i analitičko rješenje problema. Korisnički priručnik i dijagram algoritma.

kurs, dodan 17.12.2012


Analiza rješenja problema linearnog programiranja. Simpleksna metoda koja koristi simpleks tablice. Modeliranje i rješavanje LP problema na računaru. Ekonomska interpretacija optimalnog rješenja problema. Matematička formulacija transportnog problema.