Laboratorij #1 Rješavanje problema linearnog programiranja

Cilj rada Sticanje vještina rješavanja problema linearno programiranje grafička, simpleks metoda i sredstva Excel-a.

Zadatak linearnog programiranja je naučiti kako pronaći maksimalne ili minimalne vrijednosti linearne funkcije u prisustvu linearnih ograničenja. Ciljna funkcija je funkcija čija je najveća ili minimalna vrijednost pronađena. Skup varijabilnih vrijednosti na kojem se postižu maksimalne ili minimalne vrijednosti naziva se optimalno rješenje (optimalni plan), svaki drugi skup vrijednosti koji zadovoljava ograničenja naziva se prihvatljivo rješenje (izvediv plan).

Metoda geometrijskog rješenja I Razmotrite probleme linearnog programiranja na primjeru.

Primjer. Pronađite maksimalnu vrijednost ciljna funkcijaL=2x 1 +2x 2 pod datim ograničenjima

Rješenje. Konstruirajmo domen rješenja sistema ograničenja mijenjajući predznake nejednakosti u znake tačnih jednakosti:

l 1: 3x 1 -2x 2 +6=0,

l 2: 3x 1 +x 2 -3=0,

l 3:x 1 -3=0.

DWITH

2 0 1 3 X 1

(l 1) (l 3)

Pravo l 1 dijeli ravan X O at u dvije poluravnine, od kojih se mora izabrati jedna koja zadovoljava prvu nejednakost u sistemu (3). Za ovo uzimamo t. O(0; 0) i zamijeniti u nejednakosti. Ako je tačno, onda je potrebno zasjeniti poluravninu od prave linije u kojoj se nalazi tzv. O(0; 0). Uradite isto sa ravnim linijama. l 2 i l 3 . Područje rješenja nejednačina (3) je poligon ABCD. Za svaku tačku ravni, funkcija L uzima fiksnu vrijednost L=L 1 . Skup svih tačkastih struja je prava linija L=c 1 x 1 +c 2 x 2 (u našem slučaju L=2x 1 +2x 2) okomito na vektor WITH(With 1 ;With 2) (WITH(2; 2)), koji proizilaze iz izvora. Ako se ova linija pomakne u pozitivnom smjeru vektora With, zatim ciljnu funkciju Lće se povećati, inače će se smanjiti. Dakle, u našem slučaju, prava linija pri izlasku iz poligona ABCD odluke će proći IN(3; 7,5), te stoga, uklj. IN ciljna funkcija uzima maksimalnu vrijednost, tj. L max =2ּ3+2ּ7,5=21. Slično, utvrđuje se da funkcija uzima minimalnu vrijednost, tj. D(1; 0) i L min=2ּ1+2ּ0=2.

Algoritam simpleks metode za rješavanje problema linearnog programiranja je sljedeći.

1. Opšti problem linearnog programiranja svodi se na kanonski problem (postoje predznaci jednakosti u ograničenjima) uvođenjem onoliko pomoćnih varijabli koliko ima nejednakosti u sistemu ograničenja.

2. Funkcija cilja se izražava u vidu osnovnih i pomoćnih varijabli.

3. Prva simpleks tabela je sastavljena. U bazu se upisuju varijable, prema kojima je sistem ograničenja dozvoljen (najbolje je uzeti pomoćne varijable kao osnovne varijable). Prvi red tabele navodi sve varijable i pruža kolonu za slobodne članove. U zadnjem redu tabele upisani su koeficijenti funkcije cilja suprotnih predznaka

4. Svaka simpleks tabela daje rešenje za problem linearnog programiranja: slobodne varijable su jednake nuli, osnovne varijable su jednake, respektivno, slobodnim članovima.

5. Kriterijum optimalnosti je odsustvo negativnih elemenata u poslednjem redu tabele za rešavanje problema za maksimum i pozitivnih elemenata za minimum.

6. Da bi se rješenje poboljšalo, potrebno je prijeći s jedne simpleks tabele na drugu. Da biste to učinili, u prethodnoj tabeli nalazi se ključna kolona koja odgovara najmanjem negativnom elementu u zadnjem redu tabele u maksimalnom problemu i najvećem pozitivnom koeficijentu u minimalnom problemu. Zatim pronađite ključni red koji odgovara minimalnom omjeru slobodnih termina i odgovarajućih pozitivnih elemenata ključne kolone. Na raskrsnici ključnog stupca i ključnog reda nalazi se ključni element.

7. Počinjemo popunjavati sljedeću simpleks tabelu popunjavanjem baze: varijabla koja odgovara ključnom redu se izvodi iz baze, a na njeno mjesto se uvodi varijabla koja odgovara ključnoj koloni. Elementi prethodnog niza ključeva se dobijaju dijeljenjem prethodnog elementa nizom ključeva. Elementi prethodnog ključnog stupca postaju nule, osim ključnog elementa, koji je jedan. Svi ostali elementi se računaju prema pravilu pravokutnika:

8. Simpleksne tabele se transformišu dok se ne dobije optimalan plan.

Primjer. Pronađite maksimalnu vrijednost funkcije
ako su varijable
zadovoljiti sistem ograničenja:

Rješenje. 1. Uvođenje novih varijabli
, uz pomoć kojih transformišemo nejednakosti sistema u jednačine:

Mijenjamo predznak koeficijenata ciljne funkcije ili ga zapisujemo u obliku
. Popunjavamo prvu simpleks tabelu, u nulti red upisujemo X 1 ,X 2 i (slobodni koeficijenti). U koloni nula X 3 ,X 4 ,X 5 i F. Ovu tabelu popunjavamo prema dobijenom sistemu jednačina i transformisanoj funkciji cilja.

Provjeravamo kriterij optimalnosti za pronalaženje maksimalne vrijednosti: u posljednjem redu svi koeficijenti moraju biti pozitivni. Ovaj kriterij nije ispunjen, prelazimo na sastavljanje druge tabele.

2. Razlučujući element prve tablice nalazimo na sljedeći način. Među elementima posljednjeg reda biramo najveći negativni koeficijent u apsolutnoj vrijednosti (ovo je -3) i drugi stupac se prihvata kao rješavajući. Ako su svi koeficijenti kolone nepozitivni, onda
.

Da bismo odredili red za razrješenje, dijelimo slobodne koeficijente odgovarajućim elementima kolone za razrješenje i biramo minimalni omjer, a negativne koeficijente ne uzimamo. Imamo
, drugi red je dopušten. Presjek dopuštenog reda i stupca daje permisivni element - ovo je 3.

3. Popunite drugu simpleks tabelu. Varijable na čijem presjeku dobijamo razlučujući element, razmjenu, tj. I . Element omogućavanja zamjenjujemo njegovim inverznim, tj. na. Elementi permisivnog reda i stupca (osim permisivnog elementa) podijeljeni su permisivnim elementom. U ovom slučaju mijenjamo predznak koeficijenata kolone za razrješenje.

Preostali elementi druge tabele dobijaju se pravilom pravougaonika iz elemenata prve tabele. Za popunjenu ćeliju i ćeliju sa elementom za razrješenje, pravimo pravougaonik. Zatim, od elementa za ćeliju koju treba popuniti, oduzimamo proizvod elemenata druga dva vrha, podijeljen sa elementom za razrješenje. Pokažimo proračune prema ovom pravilu za popunjavanje prvog reda druge tabele:

.

Nastavljamo popunjavati tabele prema ovim pravilima dok se ne ispuni kriterij. Imamo još dva stola za naš zadatak.

	X 1	X 4					X 3	X 2
X 3						X 1
X 2						X 2
X 5						X 5

4. Rezultat ovog algoritma se bilježi na sljedeći način. U finalnoj tabeli, element na raskrsnici reda
i kolona b, daje maksimalnu vrijednost ciljne funkcije. U našem slučaju
. Vrijednosti varijabli u redovima jednake su slobodnim koeficijentima. Za naš zadatak imamo
.

Postoje i drugi načini sastavljanja i popunjavanja simpleks tabela. Na primjer, za fazu 1, sve varijable i slobodni koeficijenti se zapisuju u nulti red tabele. Nakon što pronađemo element za razrješenje prema istim pravilima u sljedećoj tabeli, zamjenjujemo varijablu u nultom stupcu, ali ne i u redu. Svi elementi permisivne linije su podijeljeni permisivnim elementom i evidentirani u novoj tabeli. Za preostale elemente kolone za rješavanje pišemo nule. Zatim izvršavamo navedeni algoritam, uzimajući u obzir ova pravila.

Prilikom rješavanja problema linearnog programiranja za minimum, najveći pozitivni koeficijent se bira u posljednjem redu, a navedeni algoritam se izvodi sve dok u posljednjem redu nema pozitivnih koeficijenata.

Rješenje zadataka linearnog programiranja pomoću Excela izvodi se na sljedeći način.

Za rješavanje problema linearnog programiranja koristi se dodatak Traži rješenje. Prvo morate biti sigurni da je ovaj dodatak prisutan na kartici Podaci u grupi Analiza (za 2003. pogledajte Alati). Ako nedostaje komanda Solver ili grupa Analyze, morate preuzeti ovaj dodatak.

Da biste to uradili, kliknite na Microsoft Office File (2010), a zatim kliknite na dugme Opcije programa Excel. U prozoru s opcijama programa Excel koji se pojavi odaberite polje Dodaci na lijevoj strani. Na desnoj strani prozora vrijednost polja Upravljanje treba postaviti na Excel dodatke, kliknite na dugme "Idi" koje se nalazi pored ovog polja. U prozoru dodataka potvrdite izbor u polju za potvrdu pored Find Solution, a zatim kliknite na OK. Tada možete raditi s instaliranim dodatkom Find Solutions.

Prije pozivanja Search Solutions, potrebno je pripremiti podatke za rješavanje problema linearnog programiranja (iz matematičkog modela) na radnom listu:

1) Odredite ćelije u koje će se smjestiti rezultat rješenja za to, u prvi red upisujemo varijable i ciljnu funkciju. Drugi red nije popunjen (promjenjive ćelije) u ovim ćelijama će se dobiti optimalan rezultat. U sljedeći red upisujemo podatke za funkciju cilja, au sljedećim redovima sistem ograničenja (koeficijenti za nepoznate). Desna strana Uvode se ograničenja (slobodni koeficijenti), ostavljajući slobodnu ćeliju nakon snimanja koeficijenata sistema ograničenja.

2) Unesite ovisnost o varijabilnim ćelijama za ciljnu funkciju i ovisnost o varijabilnim ćelijama za lijeve dijelove sistema ograničenja u preostale slobodne ćelije. Za uvođenje formule zavisnosti, zgodno je koristiti matematičku funkciju SUMPRODUCT.

Zatim morate koristiti dodatak Traži rješenje. Na kartici Podaci, u grupi Analiza izaberite Rešavač. Pojavit će se dijaloški okvir Traži rješenje, koji se mora završiti na sljedeći način:

1) Navedite ćeliju koja sadrži funkciju cilja u polju "Optimiziraj funkciju cilja" (ova ćelija mora sadržavati formulu za funkciju cilja). Odaberite opciju za optimizaciju vrijednosti ciljne ćelije (maksimiziranje, minimiziranje):

2) U polje "Promjena varijabilnih ćelija" unesite promjenjive ćelije. U sljedeće polje "Prema ograničenjima" unesite navedena ograničenja pomoću dugmeta "Dodaj". U prozoru koji se pojavi unesite ćelije koje sadrže formule za sistem ograničenja, odaberite znak ograničenja i vrijednost ograničenja (slobodni faktor):

3) Označite polje "Neka varijable bez ograničenja budu nenegativne". Odaberite metodu rješenja "Traži rješenje linearnih zadataka simpleks metodom". Nakon klika na dugme "Pronađi rešenje" počinje proces rešavanja problema. Kao rezultat, pojavljuje se dijaloški okvir "Rezultati traženja rješenja" i originalna tablica s popunjenim ćelijama za vrijednosti varijabli i optimalnu vrijednost funkcije cilja.

Primjer. Riješite problem linearnog programiranja pomoću dodatka Excel Solver: pronađite maksimalnu vrijednost funkcije
pod ograničenjima

,

;

,
.

Rješenje. Da bismo riješili naš problem na Excel radnom listu, izvršit ćemo navedeni algoritam. Početne podatke unosimo u obliku tabele

Uvodimo zavisnosti za funkciju cilja i sistem ograničenja. Da biste to učinili, u ćeliju C2 unesite formulu =SUMPRODUCT(A2:B2;A3:B3). U ćelijama C4 i C5, respektivno, formule su: =SUMPROIZVOD(A2:B2;A4:B4) i =SUMPROIZVOD(A2:B2;A5:B5). Rezultat je tabela.

Pokrećemo naredbu "Traži rješenje" i popunjavamo prozor koji se pojavi Traži rješenje na sljedeći način. U polje "Optimiziraj funkciju cilja" unesite ćeliju C2. Odlučili smo da optimiziramo vrijednost ciljne ćelije "Maksimalno".

U polje "Promjena varijabilnih ćelija" unesite promjenjive ćelije A2:B2. U polje "Prema ograničenjima" unesite navedena ograničenja pomoću dugmeta "Dodaj". Reference ćelije $C$4:$C$5 Reference ograničenja =$D$4:$D$5 znak između njih<= затем кнопку «ОК».

Označite okvir "Neograničene varijable neka budu nenegativne". Odaberite metodu rješenja "Traži rješenje linearnih zadataka simpleks metodom".

Pritiskom na dugme „Pronađi rešenje“ započinje proces rešavanja problema. Kao rezultat, pojavljuje se dijaloški okvir "Rezultati traženja rješenja" i originalna tablica s popunjenim ćelijama za vrijednosti varijabli i optimalnu vrijednost funkcije cilja.

U dijalog box-u "Rezultati traženja rješenja" pohranjujemo rezultat x1=0,75, x2=0,75 , F=1,5 - jednak maksimalnoj vrijednosti funkcije cilja.

Zadaci za samostalan rad

Vježba 1. Grafičke, simpleks metode i Excel alati za pronalaženje maksimalne i minimalne vrijednosti funkcije F(x) za dati sistem ograničenja.

1. F(x)=10x 1 +5x 2 2. F(x)=3x 1 -2x 2

3. F(x)=3x 1 +5x 2 4. F(x)=3x 1 +3x 2

5. F(x)=4x 1 -3x 2 6. F(x)=2x 1 -x 2

7. F(x)=-2x 1 +4x 2 8. F(x)=4x 1 -3x 2

9. F(x)=5x 1 +10x 2 10. F(x)=2x 1 +x 2

11. F(x)=x 1 +x 2 12. F(x)=3x 1 +x 2

13. F(x)=4x 1 +5x 2 14. F(x)=3x 1 +2x 2

15. F(x)=-x 1 -x 2 16. F(x)=-3x 1 -5x 2

17. F(x)=2x 1 +3x 2 18. F(x)=4x 1 +3x 2

19. F(x)=-3x 1 -2x 2 20. F(x)=-3x 1 +4x 2

21. F(x)=5x 1 -2x 2 22. F(x)=-2x 1 +3x 3

23. F(x)=2x 1 +3x 2 24. F(x)=4x 1 +3x 2

25. F(x)=-3x 1 -2x 2 26. F(x)=-3x 1 +4x 2

27. F(x)=-2x 1 +4x 2 28. F(x)=4x 1 -3x 2

29. F(x)=-x 1 -x 2 30. F(x)=-3x 1 -5x 2

Kontrolna pitanja.

1. Koji se zadaci nazivaju problemi linearnog programiranja?

2. Navedite primjere problema linearnog programiranja.

3. Kako se problem linearnog programiranja rješava grafičkom metodom?

4. Opisati algoritam simpleks metode za rješavanje problema linearnog programiranja.

5. Opišite algoritam za rješavanje problema linearnog programiranja koristeći Excel.

Ako postoji samo jedan ograničavajući faktor (na primjer, oskudna mašina), rješenje se može pronaći pomoću jednostavnih formula (pogledajte link na početku članka). Ako postoji nekoliko ograničavajućih faktora, koristi se metoda linearnog programiranja.

Linearno programiranje je naziv dat kombinaciji alata koji se koriste u nauci upravljanja. Ova metoda rješava problem alokacije oskudnih resursa među konkurentskim aktivnostima kako bi se maksimizirala ili minimizirala neka numerička vrijednost, kao što su marginalni dobici ili troškovi. U poslovanju se može koristiti u oblastima kao što su planiranje proizvodnje za maksimiziranje profita, odabir komponenti za minimiziranje troškova, odabir portfelja investicija za maksimiziranje profitabilnosti, optimizacija transporta robe za smanjenje udaljenosti, raspodjela osoblja za maksimiziranje radne efikasnosti i planiranje rada u kako biste uštedjeli vrijeme.

Preuzmite bilješku u , crteže u formatu

Linearno programiranje uključuje izgradnju matematičkog modela problema koji se razmatra. Nakon toga, rješenje se može pronaći grafički (o čemu se govori u nastavku), korištenjem Excel-a (razmatrat će se posebno) ili specijaliziranih računalnih programa.

Možda je konstrukcija matematičkog modela najteži dio linearnog programiranja, koji zahtijeva prevođenje problema koji se razmatra u sistem varijabli, jednačina i nejednakosti – proces koji u konačnici ovisi o vještinama, iskustvu, sposobnostima i intuiciji kompajler modela.

Razmotrimo primjer konstruiranja matematičkog modela linearnog programiranja

Nikolaj Kuznjecov vodi malu mašinsku fabriku. Sljedećeg mjeseca planira da proizvede dva proizvoda (A i B), za koje se specifična marginalna dobit procjenjuje na 2.500, odnosno 3.500 rubalja.

Proizvodnja oba proizvoda zahtijeva troškove strojne obrade, sirovina i rada (slika 1). Za izradu svake jedinice proizvoda A izdvaja se 3 sata mašinske obrade, 16 jedinica sirovina i 6 jedinica rada. Odgovarajući zahtevi za jedinicu B su 10, 4 i 6. Nikolaj predviđa da će sledećeg meseca moći da obezbedi 330 sati mašinske obrade, 400 jedinica sirovina i 240 jedinica rada. Tehnologija proizvodnog procesa je takva da se u svakom mjesecu mora proizvesti najmanje 12 jedinica proizvoda B.

Rice. 1. Upotreba i obezbjeđivanje resursa

Nikolaj želi da izgradi model kako bi odredio broj jedinica proizvoda A i B koje bi trebao proizvesti u narednih mjesec dana kako bi maksimizirao marginalni profit.

Linearni model se može izgraditi u četiri koraka.

Faza 1. Definicija varijabli

Postoji ciljna varijabla (označimo je Z) koju treba optimizirati, odnosno maksimizirati ili minimizirati (na primjer, dobit, prihod ili rashod). Nikolaj nastoji da maksimizira marginalni profit, stoga je ciljna varijabla:

Z = ukupna marginalna dobit (u rubljama) primljena u sljedećem mjesecu kao rezultat proizvodnje proizvoda A i B.

Postoji niz nepoznatih nepoznatih varijabli (označavamo ih x 1, x 2, x 3, itd.), čije vrijednosti se moraju odrediti kako bi se dobila optimalna vrijednost ciljne funkcije, koja je, u našem slučaju, je ukupni marginalni profit. Ova marža doprinosa ovisi o količini proizvedenih proizvoda A i B. Ove vrijednosti treba izračunati i stoga su varijable od interesa u modelu. Dakle, označimo:

x 1 = broj jedinica proizvoda A proizvedenih u sljedećem mjesecu.

x 2 = broj jedinica proizvoda B proizvedenih u sljedećem mjesecu.

Veoma je važno jasno definisati sve varijable; obratiti posebnu pažnju na mjerne jedinice i vremenski period na koji se varijable odnose.

Stage. 2. Konstrukcija funkcije cilja

Ciljna funkcija je linearna jednadžba koja mora biti ili maksimizirana ili minimizirana. Sadrži ciljnu varijablu izraženu u terminima željenih varijabli, tj. Z izraženu u terminima x 1 , x 2 ... kao linearnu jednačinu.

U našem primjeru, svaki proizvedeni proizvod A donosi 2500 rubalja. marginalni profit, a pri proizvodnji x 1 jedinica proizvoda A, granični profit će biti 2500 * x 1. Slično tome, granični profit od proizvodnje x 2 jedinice proizvoda B će biti 3500 * x 2. Dakle, ukupna granična dobit ostvarena u narednom mjesecu zbog proizvodnje x 1 jedinice proizvoda A i x 2 jedinice proizvoda B, odnosno ciljne varijable Z će biti:

Z = 2500 * x 1 + 3500 * x 2

Nikolaj nastoji maksimizirati ovaj pokazatelj. Dakle, funkcija cilja u našem modelu je:

Maksimiziraj Z = 2500 * x 1 + 3500 * x 2

Stage. 3. Definicija ograničenja

Ograničenja su sistem linearnih jednačina i/ili nejednačina koji ograničavaju vrijednosti traženih varijabli. Oni matematički odražavaju dostupnost resursa, tehnološke faktore, uslove marketinga i druge zahtjeve. Ograničenja mogu biti tri tipa: "manje ili jednako", "veće ili jednako", "strogo jednako".

U našem primjeru, proizvodi A i B zahtijevaju vrijeme obrade, sirovine i rad za proizvodnju, a dostupnost ovih resursa je ograničena. Obim proizvodnje ova dva proizvoda (tj. x 1 od 2 vrijednosti) će stoga biti ograničen činjenicom da količina resursa potrebnih u procesu proizvodnje ne može premašiti raspoloživu. Razmotrite situaciju s vremenom obrade stroja. Za proizvodnju svake jedinice proizvoda A potrebno je tri sata mašinske obrade, a ako se proizvede x 1 jedinica, tada će se potrošiti 3 * x 1 sat ovog resursa. Za proizvodnju svake jedinice proizvoda B potrebno je 10 sati i, prema tome, ako se proizvede x 2 proizvoda, tada će biti potrebno 10 * x 2 sata. Dakle, ukupna količina mašinskog vremena potrebnog za proizvodnju x 1 jedinice proizvoda A i x 2 jedinice proizvoda B je 3 * x 1 + 10 * x 2 . Ovo ukupno vreme mašine ne može biti duže od 330 sati. Matematički, ovo se piše na sljedeći način:

3 * x 1 + 10 * x 2 ≤ 330

Slična razmatranja se primjenjuju na sirovine i rad, dozvoljavajući zapisivanje još dva ograničenja:

16 * x 1 + 4 * x 2 ≤ 400

6 * x 1 + 6 * x 2 ≤ 240

Na kraju, treba napomenuti da postoji uvjet prema kojem se mora proizvesti najmanje 12 jedinica proizvoda B:

Faza 4. Zapisivanje uslova nenegativnosti

Željene varijable ne mogu biti negativni brojevi, koji se moraju zapisati kao nejednačine x 1 ≥ 0 i x 2 ≥ 0. U našem primjeru, drugi uvjet je suvišan, jer je gore utvrđeno da x 2 ne može biti manji od 12.

Kompletan model linearnog programiranja za Nikolajev proizvodni problem može se napisati kao:

Maksimalno: Z = 2500 * x 1 + 3500 * x 2

Pod uslovom da: 3 * x 1 + 10 * x 2 ≤ 330

16 * x 1 + 4 * x 2 ≤ 400

6 * x 1 + 6 * x 2 ≤ 240

Razmotrimo grafičku metodu za rješavanje problema linearnog programiranja.

Ova metoda je prikladna samo za probleme sa dvije potrebne varijable. Model izgrađen iznad će se koristiti za demonstraciju metode.

Ose na grafikonu predstavljaju dvije nepoznate varijable (slika 2). Nije bitno koju varijablu nacrtati duž koje ose. Važno je odabrati skalu koja će vam u konačnici omogućiti da napravite vizualni dijagram. Budući da obje varijable moraju biti ne-negativne, crta se samo 1. kvadrant.

Rice. 2. Graf osi linearnog programiranja

Razmotrimo, na primjer, prvo ograničenje: 3 * x 1 + 10 * x 2 ≤ 330. Ova nejednakost opisuje područje ispod prave: 3 * x 1 + 10 * x 2 = 330. Ova prava seče x-osu 1 kod x 2 = 0, to jest, jednadžba izgleda ovako: 3 * x 1 + 10 * 0 = 330, a njeno rješenje: x 1 = 330 / 3 = 110

Slično, izračunavamo tačke preseka sa x 1 i x 2 osama za sve uslove ograničenja:

Prihvatljiv raspon	Granica dozvoljenih vrijednosti	Presjek sa x-osom 1	Raskrsnica sa x-osom 2
3 * x 1 + 10 * x 2 ≤ 330	3 * x 1 + 10 * x 2 = 330	x 1 = 110; x 2 = 0	x 1 = 0; x 2 = 33
16 * x 1 + 4 * x 2 ≤ 400	16 * x 1 + 4 * x 2 = 400	x 1 = 25; x 2 = 0	x 1 = 0; x 2 = 100
6 * x 1 + 6 * x 2 ≤ 240	6 * x 1 + 6 * x 2 = 240	x 1 = 40; x 2 = 0	x 1 = 0; x 2 = 40
x 2 ≥ 12	x 2 = 12	ne prelazi; ide paralelno sa x-osom 1	x 1 = 0; x 2 = 12

Grafički, prvo ograničenje je prikazano na Sl. 3.

Rice. 3. Konstrukcija domena izvodljivih rješenja za prvo ograničenje

Bilo koja tačka unutar odabranog trougla ili na njegovim granicama će biti u skladu sa ovim ograničenjem. Takve tačke se nazivaju validnim, a tačke izvan trougla se nazivaju nevažećim.

Slično, mi odražavamo ostala ograničenja na grafikonu (slika 4). Vrijednosti x 1 i x 2 na ili unutar zasjenjenog područja ABCDE će biti u skladu sa svim ograničenjima modela. Takvo područje se naziva domenom prihvatljivih rješenja.

Rice. 4. Područje izvodljivih rješenja za model u cjelini

Sada, u području izvodljivih rješenja, potrebno je odrediti vrijednosti x 1 i x 2 koje maksimiziraju Z. Da biste to učinili, u jednadžbi ciljne funkcije:

Z = 2500 * x 1 + 3500 * x 2

dijelimo (ili množimo) koeficijente prije x 1 i x 2 istim brojem, tako da rezultirajuće vrijednosti padaju u raspon prikazan na grafikonu; u našem slučaju, takav raspon je od 0 do 120; tako da se koeficijenti mogu podijeliti sa 100 (ili 50):

Z = 25x 1 + 35x 2

zatim dodijelite Z vrijednost jednaku umnošku koeficijenata prije x 1 i x 2 (25 * 35 = 875):

875 = 25x 1 + 35x 2

i, konačno, pronađite točke presjeka prave sa osama x 1 i x 2:

Nacrtajmo ovu ciljnu jednačinu na graf na isti način kao i ograničenja (slika 5):

Rice. 5. Primjena funkcije cilja (crna tačkasta linija) na područje izvodljivih rješenja

Z vrijednost je konstantna u cijeloj liniji funkcije cilja. Da biste pronašli vrijednosti x 1 i x 2 koje maksimiziraju Z, potrebno je paralelno prenijeti liniju ciljne funkcije na takvu tačku unutar granica područja dopuštenih rješenja, koja se nalazi na maksimumu udaljenost od prvobitne linije funkcije cilja gore i desno, odnosno do tačke C (slika 6).

Rice. 6. Linija ciljne funkcije je dostigla svoj maksimum u području izvodljivih rješenja (u tački C)

Može se zaključiti da će se optimalno rješenje nalaziti na jednoj od krajnjih tačaka područja odlučivanja. U kojoj će zavisiti od nagiba funkcije cilja i od toga koji problem rješavamo: maksimiziranje ili minimiziranje. Dakle, nije potrebno crtati ciljnu funkciju - sve što je potrebno je odrediti vrijednosti x 1 i x 2 u svakoj od ekstremnih tačaka čitanjem sa dijagrama ili rješavanjem odgovarajućeg para jednadžbi. Pronađene vrijednosti x 1 i x 2 se zatim supstituiraju u funkciju cilja kako bi se izračunala odgovarajuća vrijednost Z. Optimalno rješenje je ono pri kojem se pri rješavanju problema maksimizacije dobije maksimalna vrijednost Z, a minimalna pri rješavanju problema minimizacije.

Odredimo, na primjer, vrijednosti x 1 i x 2 u tački C. Imajte na umu da je tačka C na presjeku pravih: 3x 1 + 10x 2 = 330 i 6x 1 + 6x 2 = 240. rješenje ovog sistema jednadžbi daje: x 1 = 10, x 2 = 30. Rezultati proračuna za sve vrhove površine izvodljivih rješenja dati su u tabeli:

Dot	Vrijednost x 1	Vrijednost x 2	Z = 2500x 1 + 3500x 2
A	22	12	97 000
IN	20	20	120 000
WITH	10	30	130 000
D	0	33	115 500
E	0	12	42 000

Dakle, Nikolaj Kuznjecom mora planirati proizvodnju 10 artikala A i 30 artikala B za sledeći mesec, što će mu omogućiti da dobije marginalni profit od 130 hiljada rubalja.

Ukratko, suština grafičke metode za rješavanje problema linearnog programiranja može se sažeti na sljedeći način:

1. Nacrtajte dvije ose na grafikonu koje predstavljaju dva parametra odlučivanja; nacrtajte samo 1. kvadrant.
2. Odredite koordinate točaka presjeka svih graničnih uvjeta sa osama, zamjenjujući vrijednosti x 1 = 0 i x 2 = 0 u jednadžbe graničnih uslova.
3. Nacrtajte linije ograničenja modela na grafikonu.
4. Odredite površinu na grafu (koja se zove dopuštena oblast odlučivanja) koja zadovoljava sva ograničenja. Ako takva regija ne postoji, onda model nema rješenje.
5. Odredite vrijednosti željenih varijabli u ekstremnim točkama područja odlučivanja i u svakom slučaju izračunajte odgovarajuću vrijednost ciljne varijable Z.
6. Za probleme maksimizacije, rješenje je tačka u kojoj je Z maksimum, a za probleme minimizacije rješenje je tačka u kojoj je Z minimum.

TEMA: LINEARNO PROGRAMIRANJE

ZADATAK 2.A. Rješavanje problema linearnog programiranja grafičkom metodom

Pažnja!

Ovo je UVODNA VERZIJA rada br. 2073, cijena originala je 200 rubalja. Dizajnirano u programu Microsoft Word.

Plaćanje. Kontakti.

Opcija 7. Pronađite maksimalnu i minimalnu vrijednostlinearna funkcija F \u003d 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:

Zamenivši uslovno znake nejednačina znacima jednakosti, dobijamo sistem jednačina x1 + x2 = 4;

- x1 + 2 x2 = 2;

x1 + 2 x2 = 10.

Konstruišemo prave prema ovim jednačinama, zatim, u skladu sa predznacima nejednačina, biramo poluravnine i dobijamo njihov zajednički deo - oblast dozvoljenih rešenja ODE - četvorougao MNPQ.

Minimalna vrijednost funkcije

tsii - 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 \u003d 20.

Opcija 8. Pronađite maksimalnu i minimalnu vrijednost

linearna funkcija F \u003d 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:

Zamenivši uslovno znake nejednačina znacima jednakosti, dobijamo sistem jednačina x1 - 4 x2 = 4;

3 x1 - x2 = 0;

Konstruišemo prave prema ovim jednačinama, zatim, u skladu sa predznacima nejednačina, biramo poluravnine i dobijamo njihov zajednički deo - oblast dozvoljenih rešenja ODE - neograničeni poligon MNPQ.

Minimalna vrijednost funkcije

cije - na pravoj liniji NP, na primjer

u tački R(4; 0)

F min = 4 + 0 = 4.

ODE nije ograničen odozgo, dakle, F max = + ∞.

Opcija 10. Pronađite maksimalnu i minimalnu vrijednost

linearna funkcija F \u003d 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.

Zamenivši uslovno znake nejednakosti znacima jednakosti, dobijamo sistem jednačina

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

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

3 x 1 = 21 (4).

Po ovim jednačinama konstruišemo prave, zatim u skladu sa predznacima nejednakosti biramo poluravnine i dobijamo njihov zajednički deo – oblast dozvoljenih rešenja ODE – poligon MNPQRS.

Konstruišemo vektor G(2; -3) i povlačimo kroz ishodište nivo line- ravno.

Pomeramo liniju nivoa u pravcu, dok vrednost F raste. U tački S(7; 0), ciljna funkcija dostiže svoj maksimum F max =2·7–3·0= = 14. Liniju nivoa pomeramo u pravcu, dok 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 \u003d x 1 - x 2 + x 3 + x 4 + x 5 - x 6

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

3 x 1 + x 2 - 4 x 3 + 2 x 6 \u003d 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 dovodimo sistem do jedinične baze

x 2 \u003d 2 - 3 x 1 + 4 x 3 - 2 x 6

x 4 \u003d 9 - x 1 - 6 x 6 (*)

x 5 \u003d 6 - x 1 - 2 x 3 - 2 x 6

Ciljna funkcija će izgledati ovako:

F \u003d 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, dok će osnovne varijable poprimiti vrijednosti x 2 = 2; x 4 \u003d 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, pa će se s povećanjem njihovih vrijednosti vrijednost F smanjiti. Uzmimo za primjer x 6. Iz 1. jednadžbe sistema (*) može se vidjeti da je povećanje vrijednosti x 6 moguće do x 6 = 1 (sve dok x 2 ³ 0). U ovom slučaju, x 1 i x 3 zadržavaju vrijednosti jednake nuli. Sada, kao osnovne varijable, uzimamo x 4, x 5, x 6, kao slobodne - x 1, x 2, x 3. Izrazimo nove osnovne varijable u terminima novih slobodnih. Get

x 6 \u003d 1 - 3/2 x 1 - 1/2 x 2 + 2 x 3

x 4 \u003d 3 + 8 x 1 + 3 x 2 - 12 x 3

x 5 \u003d 4 + 2 x 1 + x 2 - 6 x 3

F \u003d 6 + 25/2 x 1 + 7/2 x 2 - 19 x 3

Dodijelite 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ći važeće rješenje (0; 0; 0; 3; 4; 1). U ovom slučaju, F 3 \u003d 6.

Varijabla x 3 je uključena u funkciju cilja sa negativnim koeficijentom, stoga će povećanje x 3 u odnosu na nulu dovesti do smanjenja F. Iz 2. jednačine se može vidjeti da se x 3 može povećati do 1/ 4, od 3. jednačine - do 2/3 . Druga jednačina je kritičnija. Varijablu x 3 prevodimo u broj osnovnih, x 4 u broj slobodnih.

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

x 3 \u003d 1/4 + 2/3 x 1 + 1/4 x 2 - 1/12 x 4

x 5 \u003d 5/2 - 2 x 1 - 1/2 x 2 + 1/2 x 4

x 6 \u003d 3/2 - 1/6 x 1 - 1/6 x 4

Ciljna funkcija će poprimiti oblik

F \u003d 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, pa će se s povećanjem njihovih vrijednosti vrijednost F smanjiti. Uzmimo, na primjer, x 2 . Iz 2. jednadžbe sistema može se vidjeti da je povećanje vrijednosti x 2 moguće do x 2 = 5 (sve dok x 5 ³ 0). U ovom slučaju, x 1 i x 4 zadržavaju nulte vrijednosti, vrijednosti ostalih varijabli su jednake x 3 = 3/2; x 5 = 0, x 6 = 3/2, odnosno četvrto važeće rješenje (0; 5; 3/2; 0; 0; 3/2). U ovom slučaju, F 4 \u003d 5/4.

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

x 2 \u003d 5 - 4 x 1 + x 4 - 2 x 5

x 3 \u003d 3/2 - 1/3 x 1 + 1/6 x 4 - 1/2 x 5

x 6 \u003d 3/2 - 1/6 x 1 - 1/6 x 4

Ciljna funkcija će poprimiti oblik

F \u003d - 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 \u003d 30;

x 3 + x 5 - 2 x 6 \u003d 6;

2 x 4 + 3 x 5 - 2 x 6 \u003d 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, 4 varijable kao osnovne. Za slobodne biramo x 5 i x 6, kao osnovne x 1, x 2, x 3, x 4. Osnovne varijable izražavamo u terminima slobodnih i sistem jednačina svodimo na jediničnu osnovu

x 1 \u003d 12 - x 5 - x 6;

x 2 \u003d 30 - 5 x 5 + x 6;

x 3 \u003d 6 - x 5 + 2 x 6;

x 4 \u003d 9 - 3/2 x 5 + x 6;

Ciljnu funkciju zapisujemo u obliku F = 4 x 5 + 2 x 6 . Slobodnim varijablama dodijelite nulte vrijednosti 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 dobićemo prvo izvodljivo rešenje (12, 30 , 6, 9, 0,) i F 1 = 0.

Obje slobodne varijable ulaze u ciljnu funkciju sa pozitivnim koeficijentima, odnosno moguće je dalje povećanje F. Prevedemo, na primjer, x 6 u broj osnovnih. Jednačina (1) pokazuje da x 1 = 0 pri x 5 = 12, u (2) ÷ (4) x 6 ulazi 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 kroz nove slobodne

x 6 \u003d 12 - x 1 - x 5;

x 2 \u003d 42 - x 1 - 6 x 5;

x 3 \u003d 30 - 2 x 1 - 3 x 5;

x 4 \u003d 21 - x 1 - 5/2 x 5;

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

Slobodnim varijablama dodjeljujemo nulte vrijednosti 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 dobićemo drugo izvodljivo rešenje (0, 42 , 30, 21, 0, 12) i F 2 = 24.

Ciljna funkcija x 5 ulazi sa pozitivnim koeficijentom, odnosno moguće je dalje povećanje F. Pređimo na novu osnovu: osnovne varijable - x 6, x 5, x 3, x 4, slobodne - x 1 , x 2. Izrazimo nove osnovne varijable kroz new free

x 6 \u003d 5 - 5/6 x 1 + 1/6 x 2;

x 5 \u003d 7 - 1/6 x 1 - 1/6 x 2;

x 3 \u003d 9 - 3/2 x 1 + 1/2 x 2;

x 4 \u003d 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;

Slobodnim varijablama dodijelite nulte vrijednosti 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 dobićemo treće izvodljivo rešenje X 3 = (0, 0, 9, 7/2, 7, 5) i F 3 = 38.

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

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

Opcija 10. Maksimizirajte ciljnu funkciju F \u003d x 2 + x 3

pod ograničenjima: x 1 - x 2 + x 3 \u003d 1,

x 2 - 2 x 3 + x 4 \u003d 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. Dakle, dvije varijable se mogu uzeti kao slobodne, dvije druge varijable - osnovne - mogu se uzeti kao slobodne. izraženo linearno u terminima dva slobodna.

Uzmimo kao slobodne varijable x 2 i x 3. Tada će varijable x 1 i x 2 biti osnovne, koje ćemo izraziti slobodnim

x 1 \u003d 1 + x 2 - x 3; (*)

x 4 \u003d 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 .

Kod 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), dok je F 1 = 0.

Povećanje F je moguće uz povećanje, na primjer, vrijednosti x 3, koja je uključena u izraz za F sa pozitivnim koeficijentom (x 2 ostaje jednak nuli). U prvoj jednačini sistema (*) se vidi 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, mijenjajući x 1 i x 3 mjesta. Sada će osnovne varijable biti x 3 i x 4, slobodne - x 1 i x 2. Sada izražavamo x 3 i x 4 u terminima x 1 i x 2.

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

x 4 \u003d 4 - 2 x 1 + x 2;

F = x 2 + 1 - x 1 + x 2 \u003d 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), u kojem je F 2 =1.

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

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

ZADATAK 2.D. Napišite zadatak dvojan datom.

originalni zadatak.

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

s ograničenjima: x 1 + x 2 \u003d 20,

x 2 + 2× x 4 ≥ 5,

x 1 + x 2 + x 3 ≤ 8,

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

Rješenje:

Sistem ograničenja dovodimo do jednog, na primjer, kanonskog oblika uvođenjem dodatnih varijabli u 2. i 3. jednadžbu

x 1 + x 2 = 20,

x 2 + 2 × x 4 - x 5 \u003d 5,

- x 1 + x 2 + x 3 + x 6 \u003d 8.

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

Minimizirajte funkciju cilja F = 20 × y 1 + 5 × y 2 + 8 × y 3

za y 1 — y 3 ≥ 2,

y1 + y2 + y3 ≥ 0,

y 3 ≥ 0,

2× y2 ≥ 1,

Y2 ≥ 0,

y 3 ≥ 0.

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

sa ograničenjima: x 1 + 2× x 2 - x 4 + x 5 \u003d 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 originalni problem maksimizacije sa sistemom ograničenja u obliku jednačina, odnosno, par dualnih problema ima asimetričnu formu 2. tipa, čiji matematički model u matričnom obliku ima oblik:

Početni problem: Dvostruki problem:

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

kod A × X \u003d B i A T × Y ≥ C T

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

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

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

Pronađite transponiranu matricu koeficijenata, matricu-red koeficijenata za varijable u funkciji cilja i matricu-stupac slobodnih članova

0 1 0 0 V T \u003d (1; 2; 5)

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

Dualni problem se može napisati u sljedećem obliku:

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

pod ograničenjima y 1 ≥ 0,

2× y 1-4 × y 2 + 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

ograničeno: 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 originalni 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 = S × X min F \u003d B T × Ymax

kod A × X ≥ B i A T × Y ≤ C 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 \u003d (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 se formuliše kao:

Maksimiziraj funkciju cilja F = 2y 1 + 3y 2 + 4y 3

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

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

7× y 1 + 5 × y 2 + 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

pod 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:

Sistem ograničenja svodimo na 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. Odaberemo x 1 , z 1 , z 3 kao osnovne 3 varijable, x 2 , x 3 , x 4 , z 2 kao slobodne, kroz njih izražavamo osnovne varijable.

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

Zamjena u (1) i (3), dobijamo

x 1 - 2 x 2 + 5 x 3 - 3 x 4 - z 2 \u003d 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 \u003d 2.

Sastavite simpleks tabelu

I iteracija Tabela 1

Basic AC	Sloboda. AC
x 1	1	1	— 2	5	— 3	0	— 1	0		3/8
z1	2	0	7	-11		1	2	0	1/ 4	1/8
z3	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
x4	1/ 4	0	7/8	-11/8	1	1/8	2/8	0		11/7
z3	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 \u003d (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
x4	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 \u003d (1; 0; 6/7; 10/7; 0; 0; 0) F 3 = 52/7.

IV iteracija Tabela 4

z1	1/ 2	1/2	— 3	0	0	1	-1/2	-1/2
x4	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 \u003d (0; 0; 25/14; 37/14; 1/2; 0; 0) F 4 = 149/14.

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

Odgovor: F max = 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 \u003d 3,

x 2 + 2 x 4 \u003d 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. Uzimamo x 3, x 4 kao slobodne varijable, osnovne varijable x 1, x 2 ćemo izraziti u terminima slobodnih i dovodimo sistem do jedinične baze:

x 2 \u003d 1 - 2 x 4,

x 1 = 3 - x 2 - 2 x 3 + x 4 = 3 - 1 + 2 x 4 - 2 x 3 + x 4 \u003d 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 \u003d 10 - 11 x 3 + 15 x 4

Zapisujemo sistem jednadžbi i ciljnu funkciju u obliku pogodnom za simpleks tablicu, tj. x 2 + 2 x 4 = 1,

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

F + 11 x 3 - 15 x 4 \u003d 10

Hajde da napravimo sto

I iteracija Tabela 1

Basic AC	Sloboda. AC
x1	2	1	0		— 3		1/2
x2	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

x3	1	1/2	0	1	-3/2		3/4
x2	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

x3	7/4	1/2	3/4	1	0
x4	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, odnosno u izrazu za ciljnu funkciju, nema pozitivnih brojeva, svi 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. Minimizirajte ciljnu funkciju F \u003d x 1 + x 2,

s ograničenjima: x 1 -2 x 3 + x 4 \u003d 2,

x 2 - x 3 + 2 x 4 \u003d 1,

Rješenje:

Broj varijabli je 5, rang matrice je ​​​​​​, stoga je broj slobodnih varijabli r \u003d 6-3 \u003d 2. Uzimamo x 3 i x 4 kao slobodne varijable, x 1, x 2, x 5 kao osnovne. Sve jednačine sistema su već svedene na jednu osnovu (osnovne varijable se izražavaju u terminima slobodnih), ali su napisane u obliku koji nije pogodan za korišćenje simpleks tabela. Sistem jednačina zapisujemo u obliku

x 1 - 2 x 3 + x 4 \u003d 2

x 2 - x 3 +2 x 4 \u003d 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 poslednje 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 je (3/2; 0; 0; 1/2; 11/2).

Odredite grafičkom metodom maksimum funkcije cilja

F= 2x 1 + 3x 2 ® max

Uz ograničenja

Rješenje koristeći Excel tabele

Prvo gradimo na listu excel rješenje sistema nejednakosti.

Razmotrimo prvu nejednakost.

Konstruirajmo graničnu liniju iz dvije tačke. Označite liniju sa (L1) (ili Red1). Koordinate X 2 računamo prema formulama:

Da biste izgradili, odaberite dijagram raspršenja

Odabir podataka za pravu liniju

Promijenite naziv linije:

Odaberite izgled grafikona. Promijenite naziv koordinatnih osa:

Prava linija (L1) na grafikonu:

Rješenje stroge nejednakosti može se naći korištenjem jedne ispitne točke koja ne pripada pravoj (L1). Na primjer, koristeći tačku (0; 0)W(L1).

0+3×0< 18 или 0 < 18 .

Nejednakost je tačna, stoga će rješenje nejednakosti (1) biti poluravnina u kojoj se nalazi ispitna točka (na slici ispod linije L1).

Tada rješavamo nejednakost (2) .

Konstruirajmo graničnu liniju 2 iz dvije tačke. Označite liniju sa (L2).

Prava linija (L2) na grafikonu:

Rješenje stroge nejednakosti 2 može se naći korištenjem jedine ispitne točke koja ne pripada pravoj (L2). Na primjer, koristeći tačku (0; 0)W(L2).

Zamjenom koordinata tačke (0; 0) dobijamo nejednakost

2×0 + 0< 16 или 0 < 16 .

Nejednakost je tačna, stoga će rješenje nejednakosti (2) biti poluravnina u kojoj se nalazi ispitna točka (na donjoj slici prava L2).

Tada rješavamo nejednakost (3) .

Konstruirajmo graničnu liniju iz dvije tačke. Označite liniju sa (L3).

Prava linija (L3) na grafikonu:

Rješenje stroge nejednakosti 2 može se naći korištenjem jedine ispitne točke koja ne pripada pravoj (L3). Na primjer, koristeći tačku (0; 0)W(L3).

Zamjenom koordinata tačke (0; 0) dobijamo nejednakost

Nejednakost je tačna, stoga će rješenje nejednakosti (3) biti poluravnina u kojoj se nalazi ispitna točka (na donjoj slici, linija L3).

Tada rješavamo nejednakost (4) .

Konstruirajmo graničnu liniju iz dvije tačke. Označite liniju sa (L4).

Dodajte podatke u Excel tablicu

Prava linija (L4) na grafikonu:

Rješenje stroge nejednakosti 3 X 1 < 21 можно найти с помощью единственной пробной точки, не принадлежащей прямой (L4). Например, с помощью точки (0; 0)Ï(L4).

Zamjenom koordinata tačke (0; 0) dobijamo nejednakost

Nejednakost je tačna, stoga će rješenje nejednakosti (4) biti poluravnina u kojoj se nalazi ispitna točka (lijevo od prave L4 na slici).

Rješavanjem dvije nejednačine (5) i (6)

je 1. četvrtina omeđena koordinatnim linijama i .

Sistem nejednakosti je riješen. Rješenje sistema nejednačina (1) - (6) u ovom primjeru je konveksni poligon u donjem lijevom uglu slike, omeđen linijama L1, L2, L3, L4 i koordinatnim linijama i . Možete se uvjeriti da je poligon ispravno odabran zamjenom ispitne tačke, na primjer (1; 1) u svaku nejednakost originalnog sistema. Zamjenom tačke (1; 1) dobijamo da su sve nejednakosti, uključujući prirodna ograničenja, tačne.

Razmotrimo sada funkciju cilja

F= 2x 1 + 3x 2 .

Napravimo linije nivoa za vrijednosti funkcije F=0 I F=12(numeričke vrijednosti se biraju proizvoljno). Dodajte podatke u Excel tablicu

Linije nivoa na grafikonu:

Konstruirajmo vektor pravaca (ili gradijent) (2; 3). Koordinate vektora se poklapaju sa koeficijentima funkcije cilja F.

Uvod

Moderna faza ljudskog razvoja je drugačija po tome što se vijek energije zamjenjuje dobom informatike. Intenzivno se uvode nove tehnologije u sve sfere ljudskog djelovanja. Rises pravi problem prelazak na Informaciono društvo kojima razvoj obrazovanja treba da postane prioritet. Struktura znanja u društvu se također mijenja. Temeljna znanja koja doprinose kreativnom razvoju pojedinca postaju sve važnija za praktični život. Važna je i konstruktivnost stečenog znanja, sposobnost njegovog strukturiranja u skladu sa ciljem. Na osnovu znanja formiraju se novi informacioni resursi društva. Formiranje i sticanje novih znanja treba da se zasniva na strogoj metodologiji sistematskog pristupa, u okviru koje posebno mesto zauzima modelski pristup. Mogućnosti pristupa modeliranju su izuzetno raznolike kako u pogledu formalnih modela koji se koriste, tako iu pogledu načina implementacije metoda modeliranja. Fizičko modeliranje omogućava dobijanje pouzdanih rezultata za prilično jednostavne sisteme.

Trenutno je nemoguće imenovati oblast ljudske aktivnosti u kojoj se, u jednom ili drugom stepenu, ne bi koristile metode modeliranja. Ovo posebno važi za upravljanje različitim sistemima, gde su glavni procesi donošenja odluka na osnovu primljenih informacija.

1. Izjava o problemu

minimalna funkcija cilja

Riješiti problem nalaženja minimuma funkcije cilja za sistem ograničenja specificiranih poligonom odluke u skladu sa opcijom br. 16 zadatka. Poligon odluke je prikazan 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 za rješavanje LP problema;

Algebarska metoda za rješavanje LP problema;

Simpleksna metoda za rješavanje LP problema;

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

Rješavanje dvojnog LP problema;

Metoda "grana i granica" za rješavanje cjelobrojnih LP problema;

Gomoryjeva metoda za rješavanje cjelobrojnih LP problema;

Balash metoda za rješavanje Booleovih LP problema.

Usporedite rezultate rješenja različitim metodama kako biste izveli odgovarajuće zaključke o radu.

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. Pogodno za kvalitativno istraživanje svojstva rješenja i koristi se u sprezi s drugim metodama (algebarskim, granama i vezama, itd.). Ideja metode je zasnovana na grafičkom rješenju sistema linearnih nejednačina.

Rice. 2 Grafičko rješenje LP problema

Niska tačka

Jednačina prave koja prolazi kroz dvije tačke A1 i A2:

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

Sunce: (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 algebarskom simpleks metodom

Primjena algebarske metode za rješavanje problema zahtijeva generalizaciju reprezentacije LP problema. Originalni sistem ograničenja dat u obliku nejednakosti se pretvara u standardnu ​​notaciju kada su ograničenja data u obliku jednakosti. Pretvaranje sistema ograničenja u standardni oblik uključuje sljedeće korake:

Transformirajte nejednakosti na način da su varijable i slobodni članovi na lijevoj strani, a 0 na desnoj strani, tj. da lijeva strana bude veća ili jednaka nuli;

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

Uvodeći dodatna ograničenja na nenegativnost dodatih varijabli, zamijenite znakove nejednakosti strogim predznacima jednakosti.

Prilikom rješavanja LP problema algebarska metoda dodaje se uslov: funkcija cilja mora težiti minimumu. Ako ovo stanje nije zadovoljeno, potrebno je na odgovarajući način transformirati ciljnu funkciju (pomnožiti sa -1) i riješiti problem minimizacije. Nakon što se pronađe rješenje, zamijenite vrijednosti varijabli u originalnoj funkciji 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. Ako 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 postigla navedena ograničenja. Pretpostavlja se da je vrijednost svih slobodnih varijabli nula.

Algebarska metoda za rješavanje problema linearnog programiranja je jedna od najčešćih efikasne metode prilikom ručnog rješavanja problema male dimenzije. ne zahtijeva veliki broj aritmetičkih proračuna. Mašinska implementacija ove metode je složenija nego, na primjer, za simpleks metodu, jer algoritam za rješavanje algebarske metode je u određenoj mjeri heuristički i efikasnost rješenja u velikoj mjeri zavisi od ličnog iskustva.

slobodne varijable

St. lane - dodati. komplet

Uslovi nenegativnosti su zadovoljeni, 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šavanje korištenjem simpleks tablice.

Sve jednačine sistema svedemo 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 relaciju za sve pozitivne. 3/3; 9/1;- minimalni odnos u redu x3. Dakle - opći niz i =3 - opći element.

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

U sve nepopunjene donje kutove opće linije unosimo proizvod vrijednosti u gornji kut ć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 gradimo novu tabelu u kojoj su oznake ćelija elemenata opšte kolone i reda obrnute (x2 i x3);

U gornjem uglu bivšeg opšteg reda i stupca upisane su vrijednosti koje su prethodno bile u donjem uglu;

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 izvodljivog 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 IZVODIVOG RJEŠENJA: Da bismo pronašli izvodljivo rješenje za sistem (1), minimiziramo oblik (3) pod ograničenjima (2), kao slobodne nepoznanice 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 biti izvodljivo rješenje za sistem (1).

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

Izvorni sistem:

Koristi se uslov problema iz prethodne teme.

Dodajmo dodatne varijable:

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

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. Dvostruki problem linearnog programiranja

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

uz ograničenja:

Rješenje: Sistem ograničenja dovodimo u standardni obrazac:

Zadatak dvojan ovom će izgledati ovako:

Dualni problem će se riješiti simpleks metodom.

Transformirajmo ciljnu funkciju tako da se riješi problem minimizacije i zapiš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četni simpleks tabelu 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 je vrijednost funkcije cilja direktnog i dualnog problema ista, rješenje direktnog problema je pronađeno i jednako je 12.

Fmin \u003d Fmax = -12

7. Rješavanje problema cjelobrojnog linearnog programiranja metodom “grane i granice”.

Transformirajmo originalni problem na takav način da pri rješavanju konvencionalnim metodama ne bude zadovoljen cjelobrojni uvjet.

Početni poligon rješenja problema cjelobrojnog programiranja.

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

Sistem ograničenja zapisujemo u obliku jednakosti, za rješavanje algebarskom metodom.

Kao rezultat rješenja pronađen je optimalni plan zadatka: x1 = 9/4, x2 = 5/2, F = -41/4. Ovo rješenje ne ispunjava uvjet integralnosti postavljen u problemu. Originalni poligon rješenja dijelimo na dva regiona, isključujući regiju 3 iz njega

Promijenjen poligon rješenja problema

Sastavimo nove sisteme ograničenja za formirana područja poligona rješenja. Lijevo područje je četverougao (trapez). Sistem ograničenja za lijevu regiju poligona rješenja prikazan je u nastavku.

Sistem ograničenja za lijevu oblast

Desno područje predstavlja tačku C.

Sistem ograničenja za pravu oblast odlučivanja je predstavljen u nastavku.

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

Kao rezultat rješenja pronađen je optimalni plan zadatka: x1 = 3, x2 = 3, F = -12. Ovaj plan zadovoljava uvjet cjelobrojnih varijabli u problemu i može se uzeti kao optimalni referentni plan za originalni cjelobrojni problem linearnog programiranja. Nema smisla provoditi rješenje za pravu regiju rješenja. Slika ispod prikazuje napredak rješavanja problema cjelobrojnog linearnog programiranja u obliku stabla.

Tok rješavanja problema cjelobrojnog linearnog programiranja metodom Gomory.

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

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

Gomory 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) Simpleks metodom se utvrđuje rešenje zadatka (1), (2), za koje se ukida zahtev da rešenje bude celobrojno; 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, dobiveno 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 sa razlomačnim slobodnim članom svi ostali koeficijenti pokažu kao cijeli brojevi, tada nema cijelih brojeva, tačaka u dopuštenom poliedru i problem cjelobrojnog programiranja nema rješenja;

U suprotnom, uvodi se dodatno linearno ograničenje, koje odseca od dozvoljenog poliedra deo koji nije obećavajući za pronalaženje rešenja celobrojnog programskog problema;

3) Da biste konstruirali dodatno linearno ograničenje, odaberite l-ti red s razlomačnim slobodnim članom i zapišite dodatno ograničenje

gdje i su, respektivno, 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 niži cijeli brojevi za i, respektivno.

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

Rješenje: Reduciramo sistem linearnih ograničenja i funkciju cilja na kanonski oblik:

Odredimo optimalno rješenje sistema linearnih ograničenja, privremeno odbacivši cjelobrojni uslov. Za to koristimo simpleks metodu. Tablice u nastavku sekvencijalno prikazuju početno rješenje problema, a date su transformacije originalne tablice kako bi se dobilo optimalno rješenje problema:

Rješavanje Booleovih LP problema Balash metodom.

Sastavite vlastitu varijantu za problem cjelobrojnog 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 ciljna funkcija biraju se proizvoljno, ali u takvom način na koji je sistem ograničenja kompatibilan. Zadatak je riješiti ZCLP sa Booleovim varijablama koristeći Balash algoritam i utvrditi smanjenje računske složenosti u odnosu na rješavanje problema iscrpnim pretraživanjem.

Izvršenje ograničenja

F vrijednost

Ograničenje filtera:

Kalkulacija Određivanje smanjenja

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

Zaključak

Proces projektovanja informacionih sistema koji implementiraju novu informatičku tehnologiju stalno se unapređuje. Sve složeniji sistemi postaju u fokusu pažnje sistemskih inženjera, što otežava upotrebu fizičkih modela i povećava značaj matematičkih modela i kompjuterske simulacije sistema. Mašinsko modeliranje postalo je efikasan alat za istraživanje i projektovanje složenih sistema. Relevantnost matematičkih modela je u stalnom porastu zbog njihove fleksibilnosti, adekvatnosti stvarnim procesima, niske cijene implementacije na bazi modernih PC-a. 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 omogućili su 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 dešavaju u realnim sistemima, odnosno 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. Chernikova, N.Z. Shor. - K.: "Viša škola", 1975, 372 str.

2. Smjernice za realizaciju predmetnog projekta iz discipline "Primijenjena matematika" za studente specijalnosti "Računarski sistemi i mreže" redovni i vanredni oblici obrazovanja / Sastavili: I.A. Balakireva, A.V. Skatkov - Sevastopolj: 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. - 31s.

4. Smjernice za izučavanje discipline "Primijenjena matematika" za studente specijalnosti "Računarski sistemi i mreže" Odjeljak "Rješavanje problema cjelobrojnog linearnog programiranja" redovnog i dopisnog oblika obrazovanja / Sastavili: I.A. Balakireva, A.V. Skatkov - Sevastopolj : Izdavačka kuća SevNTU, 2000. - 13 str.

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

6. Proc. dodatak za studentsku ekonomiju. specijalista. univerziteti.-M.: Viši. škola, 1986.- 319s., ilustr.

7. Andronov S.A. Metode optimalnog dizajna: Tekst predavanja / SPbGUAP. SPb., 2001. 169 str.: ilustr.

Slični dokumenti

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

seminarski rad, 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šavanja. Analiza optimalnog rješenja. Rješenje problema jednoindeksnog linearnog programiranja. Izjava o problemu i unos podataka. Izgradnja modela i koraci rješenja.

seminarski rad, dodan 09.12.2008


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

seminarski rad, dodan 31.10.2014


Izgradnja matematičkog modela u cilju maksimizacije profita preduzeća, grafičko rešenje problema. Rješavanje problema korištenjem SOLVER dodatka. Analiza promjena u rezervama resursa. Određivanje granica promjene koeficijenata funkcije cilja.

seminarski rad, 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.

seminarski rad, dodan 13.10.2008


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

test, dodano 02.05.2012


Rješavanje problema linearnog programiranja simpleks metodom: postavljanje problema, izgradnja ekonomskog i matematičkog modela. Rješenje 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 algoritamska šema.

seminarski rad, dodan 17.12.2012


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