Konstruirajmo na ravnini skup dopustivih rješenja sustava linearne nejednakosti i geometrijski pronaći minimalna vrijednost objektivna funkcija.

Pravce gradimo u koordinatnom sustavu x 1 x 2

Nalazimo poluravnine definirane sustavom. Kako su nejednakosti sustava zadovoljene za bilo koju točku odgovarajuće poluravnine, dovoljno ih je provjeriti za bilo koju točku. Koristimo točku (0;0). Zamijenimo njegove koordinate u prvu nejednadžbu sustava. Jer , tada nejednadžba definira poluravninu koja ne sadrži točku (0;0). Slično definiramo i preostale poluravnine. Skup izvedivih rješenja nalazimo kao zajednički dio dobivenih poluravnina - to je osjenčano područje.

Konstruiramo vektor i liniju nulte razine okomitu na njega.

Pomičući ravnu liniju (5) u smjeru vektora vidimo da će najveća točka područja biti u točki A sjecišta prave (3) i prave (2). Nalazimo rješenje sustava jednadžbi:

To znači da smo shvatili poantu (13;11) i.

Pomičući ravnu liniju (5) u smjeru vektora vidimo da će minimalna točka područja biti u točki B sjecišta prave (1) i prave (4). Nalazimo rješenje sustava jednadžbi:

To znači da smo shvatili točku (6;6) i.

2. Tvrtka za proizvodnju namještaja proizvodi kombinirane ormare i računalne stolove. Njihova proizvodnja ograničena je dostupnošću sirovina (visokokvalitetne ploče, okovi) i vremenom rada strojeva koji ih obrađuju. Za svaki ormarić potrebno je 5 m2 dasaka, za stol - 2 m2. Oprema košta 10 dolara za jedan ormarić i 8 dolara za jedan stol. Tvrtka od svojih dobavljača može dobiti do 600 m2 ploča mjesečno i pribor u vrijednosti od 2000 dolara. Za svaki ormarić potrebno je 7 sati rada stroja, a za stol 3 sata. Mjesečno se može koristiti ukupno 840 radnih sati stroja.

Koliko bi kombiniranih ormarića i računalnih stolova tvrtka trebala proizvesti mjesečno da bi povećala profit ako jedan ormarić donosi 100 USD dobiti, a svaki radni stol 50 USD?

• 1. Izraditi matematički model problema i riješiti ga simpleks metodom.
• 2. Izradi matematički model dualnog problema, zapiši njegovo rješenje na temelju rješenja izvornog.
• 3. Utvrditi stupanj oskudnosti korištenih resursa i opravdati isplativost optimalnog plana.
• 4. Istražite mogućnosti daljnjeg povećanja proizvodnje ovisno o korištenju svake vrste resursa.
• 5. Procijeniti izvedivost uvođenja nove vrste proizvoda - police za knjige, ako proizvodnja jedne police košta 1 m 2 dasaka i pribora za 5 dolara, a potrebno je utrošiti 0,25 sati rada stroja i dobit od prodaje jedne police je 20 dolara.
• 1. Izgradimo matematički model za ovaj problem:

Označimo s x 1 obujam proizvodnje ormara, a x 2 - obujam proizvodnje stolova. Kreirajmo sustav ograničenja i funkciju cilja:

Zadatak rješavamo simpleks metodom. Zapišimo to u kanonskom obliku:

Zapišimo podatke zadatka u obliku tablice:

Tablica 1

Jer sad je sve delta veći od nule, onda je daljnje povećanje vrijednosti funkcije cilja f nemoguće i dobili smo optimalan plan.

Ako postoji samo jedan ograničavajući čimbenik (na primjer, oskudan stroj), rješenje se može pronaći korištenjem jednostavne formule(vidi poveznicu na početku članka). Ako postoji više ograničavajućih faktora, koristi se metoda linearnog programiranja.

Linearno programiranje je naziv za kombinaciju alata koji se koriste u znanosti upravljanja. Ova metoda rješava problem raspodjele oskudnih resursa među konkurentskim aktivnostima kako bi se maksimizirale ili minimizirale određene numeričke vrijednosti, kao što su marža doprinosa ili troškovi. U poslovanju se može koristiti u područjima kao što je planiranje proizvodnje za maksimiziranje profita, odabir komponenti za smanjenje troškova, odabir portfelja ulaganja za maksimiziranje povrata, optimiziranje prijevoza robe radi smanjenja udaljenosti, dodjeljivanje osoblja radi maksimiziranja radne učinkovitosti i planiranje radite kako biste uštedjeli vrijeme.

Preuzmite bilješku u formatu, slike u formatu

Linearno programiranje uključuje konstruiranje matematičkog modela problema koji se razmatra. Nakon čega se rješenje može pronaći grafički (razmotreno u nastavku), s koristeći Excel(razmatrat će se zasebno) ili specijaliziranih računalnih programa.

Možda je konstrukcija matematičkog modela najviše teži dio linearno programiranje, koje zahtijeva prevođenje problema koji se razmatra u sustav varijabli, jednadžbi i nejednakosti – proces koji u konačnici ovisi o vještinama, iskustvu, sposobnostima i intuiciji modelara.

Razmotrimo primjer konstruiranja matematičkog modela linearnog programiranja

Nikolay Kuznetsov upravlja malim mehaničko postrojenje. Sljedeći mjesec planira proizvesti dva proizvoda (A i B), za koje se specifična granična dobit procjenjuje na 2500 odnosno 3500 rubalja.

Oba proizvoda zahtijevaju strojnu obradu, sirovine i troškove rada (Slika 1). Svaka jedinica proizvoda A zahtijeva 3 sata strojne obrade, 16 jedinica sirovina i 6 jedinica rada za proizvodnju. Odgovarajući jedinični zahtjevi za proizvod B su 10, 4 i 6. Nicholas predviđa da sljedeći mjesec može isporučiti 330 sati strojne obrade, 400 jedinica sirovina i 240 jedinica rada. Tehnologija proizvodnog procesa je takva da se u svakom danom mjesecu mora proizvesti najmanje 12 jedinica proizvoda B.

Riža. 1. Korištenje i osiguranje resursa

Nikolai želi izgraditi model za određivanje broja jedinica proizvoda A i B koje mora proizvesti u sljedećem mjesecu kako bi maksimizirao svoju maržu doprinosa.

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

Korak 1: Definiranje varijabli

Postoji ciljana varijabla (nazovimo je Z) koju treba optimizirati, odnosno maksimizirati ili minimizirati (primjerice, dobit, prihod ili rashod). Nikolay nastoji maksimizirati maržu doprinosa, stoga ciljna varijabla:

Z = ukupna granična dobit (u rubljima) ostvarena u sljedećem mjesecu kao rezultat proizvodnje proizvoda A i B.

Postoji niz nepoznatih nepoznatih varijabli (označimo ih x 1, x 2, x 3, itd.), čije se vrijednosti moraju odrediti da bi se dobila optimalna vrijednost funkcije cilja, što je u našem slučaju ukupni granični profit. Ova marža doprinosa ovisi o proizvedenim količinama proizvoda A i B, te stoga one predstavljaju željene varijable 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.

Vrlo je važno sve jasno definirati varijable; posebnu pozornost Obratite pozornost na mjerne jedinice i vremensko razdoblje na koje se varijable odnose.

Pozornica. 2. Konstrukcija funkcije cilja

Ciljna funkcija je linearna jednadžba koja mora biti maksimizirana ili minimizirana. Sadrži ciljnu varijablu izraženu pomoću ciljnih varijabli, to jest Z izraženo u smislu x 1, x 2 ... u obliku linearne jednadžbe.

U našem primjeru, svaki proizvedeni proizvod A donosi 2500 rubalja. granični profit, a kada se proizvodi x 1 jedinica proizvoda A, granični profit će biti 2500 * x 1. Slično, granična dobit od proizvodnje x 2 jedinice proizvoda B bit će 3500 * x 2. Dakle, ukupna granična dobit ostvarena u idućem mjesecu proizvodnjom x 1 jedinica proizvoda A i x 2 jedinice proizvoda B, odnosno ciljne varijable Z bit će:

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

Pozornica. 3. Definirajte ograničenja

Ograničenja su sustav linearne jednadžbe i/ili nejednakosti koje ograničavaju vrijednosti traženih varijabli. Oni matematički odražavaju dostupnost resursa, tehnološke čimbenike, tržišne uvjete i druge zahtjeve. Ograničenja mogu biti tri tipa: "manje ili jednako", "veće ili jednako", "strogo jednako".

U našem primjeru, proizvodnja proizvoda A i B zahtijeva vrijeme strojne obrade, sirovine i rad, a dostupnost ovih resursa je ograničena. Obim proizvodnje ova dva proizvoda (to jest, vrijednosti x 1 x 2) stoga će biti ograničen činjenicom da količina resursa potrebnih u procesu proizvodnje ne može premašiti one dostupne. Razmotrimo situaciju s vremenom strojne obrade. Proizvodnja svake jedinice proizvoda A zahtijeva tri sata strojne obrade, a ako se proizvede x 1 jedinica, tada će se potrošiti 3 * x 1 sat ovog resursa. Svaka jedinica proizvoda B zahtijeva 10 sati za proizvodnju i stoga ako se proizvede x 2 proizvoda, tada će biti potrebno 10 * x 2 sata. Dakle, ukupna količina strojnog vremena potrebnog za proizvodnju x 1 jedinica proizvoda A i x 2 jedinice proizvoda B je 3 * x 1 + 10 * x 2 . Ovaj opće značenje strojno vrijeme ne može premašiti 330 sati. Matematički se to piše na sljedeći način:

3 * x 1 + 10 * x 2 ≤ 330

Slična razmatranja vrijede za sirovine i rad, što nam omogućuje da zapišemo 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 mora biti proizvedeno najmanje 12 jedinica proizvoda B:

Faza 4. Pisanje uvjeta nenegativnosti

Tražene varijable ne mogu biti negativni brojevi, koje je potrebno napisati u obliku nejednakosti 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 proizvodni zadatak Nikola se može napisati kao:

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

Pod uvjetom da je: 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 s dvije nepoznate varijable. Gore konstruirani model koristit će se za demonstraciju metode.

Osi na grafikonu predstavljaju dvije varijable od interesa (Slika 2). Nije važno koja je varijabla iscrtana duž koje osi. Važno je odabrati mjerilo koje će vam u konačnici omogućiti izgradnju vizualni dijagram. Budući da obje varijable moraju biti nenegativne, crta se samo 1. kvadrant.

Riža. 2. Osi grafova linearnog programiranja

Razmotrimo, na primjer, prvo ograničenje: 3 * x 1 + 10 * x 2 ≤ 330. Ova nejednakost opisuje područje ispod crte: 3 * x 1 + 10 * x 2 = 330. Ova linija siječe os x 1 na x 2 = 0, odnosno jednadžba izgleda ovako: 3 * x 1 + 10 * 0 = 330, a njeno rješenje: x 1 = 330 / 3 = 110

Slično, izračunavamo točke sjecišta s osi x1 i x2 za sve uvjete ograničenja:

Raspon prihvatljivih vrijednosti	Granica prihvatljivih vrijednosti	Sjecište s x-osi 1	Sjecište s x-osi 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 s x osi 1	x 1 = 0; x 2 = 12

Grafički je prvo ograničenje prikazano na sl. 3.

Riža. 3. Konstrukcija područja izvedivih rješenja za prvo ograničenje

Bilo koja točka unutar odabranog trokuta ili na njegovim granicama zadovoljit će ovo ograničenje. Takve točke nazivamo važećim, a točke izvan trokuta nevažećim.

Na sličan način prikazujemo preostala ograničenja na grafikonu (slika 4). Vrijednosti x 1 i x 2 na ili unutar osjenčane regije ABCDE zadovoljit će sva ograničenja modela. Ovo područje se naziva područjem izvedivih rješenja.

Riža. 4. Područje izvedivih rješenja za model u cjelini

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

Z = 2500 * x 1 + 3500 * x 2

podijelite (ili pomnožite) koeficijente ispred x 1 i x 2 s istim brojem, tako da dobivene vrijednosti budu unutar raspona prikazanog na grafikonu; u našem slučaju, ovaj raspon je od 0 do 120; tako da se izgledi mogu podijeliti sa 100 (ili 50):

Z = 25x 1 + 35x 2

zatim dodijelite Z vrijednost jednak umnošku koeficijenti ispred x 1 i x 2 (25 * 35 = 875):

875 = 25x 1 + 35x 2

i konačno, pronađite točke sjecišta pravca s x 1 i x 2 osi:

Iscrtajmo ovu ciljnu jednadžbu na grafu sličnom ograničenjima (Sl. 5):

Riža. 5. Primjena funkcije cilja (crna točkasta linija) na područje izvedivih rješenja

Vrijednost Z je konstantna kroz liniju funkcije cilja. Da biste pronašli vrijednosti x 1 i x 2 koje maksimiziraju Z, morate paralelno pomaknuti liniju funkcije cilja do točke unutar granica područja mogućih rješenja, koja se nalazi na najvećoj udaljenosti od izvorne linije funkcije cilja gore i desno, odnosno do točke C (sl. 6).

Riža. 6. Pravac funkcije cilja je dosegao maksimum unutar područja mogućih rješenja (u točki C)

Može se zaključiti da optimalno rješenje nalazit će se na jednoj od krajnjih točaka područja odlučivanja. Koji će ovisiti o kutu nagiba funkcije cilja i o tome koji problem rješavamo: maksimiziranje ili minimiziranje. Dakle, nije potrebno crtati funkciju cilja - sve što je potrebno je odrediti vrijednosti x 1 i x 2 u svakoj ekstremnoj točki čitanjem iz dijagrama ili rješavanjem odgovarajućeg para jednadžbi. Pronađene vrijednosti x 1 i x 2 zatim se zamjenjuju u funkciju cilja kako bi se izračunala odgovarajuća vrijednost Z. Optimalno rješenje je ono koje dobiva maksimalnu vrijednost Z pri rješavanju problema maksimizacije, a minimalnu pri rješavanju problem minimizacije.

Odredimo, na primjer, vrijednosti x 1 i x 2 u točki C. Imajte na umu da se točka C nalazi na sjecištu linija: 3x 1 + 10x 2 = 330 i 6x 1 + 6x 2 = 240. Rješavanjem ovog sustava jednadžbi dobiva se: x 1 = 10, x 2 = 30. Rezultati proračuna za sve vrhove područja mogućih rješenja dati su u tablici:

Točka	Vrijednost x 1	Vrijednost x 2	Z = 2500x 1 + 3500x 2
A	22	12	97 000
U	20	20	120 000
S	10	30	130 000
D	0	33	115 500
E	0	12	42 000

Dakle, Nikolai Kuznets mora planirati za sljedeći mjesec proizvodnju 10 proizvoda A i 30 proizvoda B, što će mu omogućiti marginalnu dobit od 130 tisuća rubalja.

Ukratko, bit grafičke metode za rješavanje problema linearnog programiranja može se navesti na sljedeći način:

1. Na grafu nacrtajte dvije osi koje predstavljaju dva parametra rješenja; nacrtajte samo 1. kvadrant.
2. Odredite koordinate točaka sjecišta svih rubnih uvjeta s osi, zamjenjujući naizmjenično vrijednosti x 1 = 0 i x 2 = 0 u jednadžbe rubnih uvjeta.
3. Iscrtajte linije ograničenja modela na grafikonu.
4. Odredite područje na grafikonu (koje se zove područje moguće odluke) koje zadovoljava sva ograničenja. Ako takva regija ne postoji, tada model nema rješenja.
5. Odredite vrijednosti traženih varijabli u ekstremne točke područja odlučivanja, te u svakom slučaju izračunati odgovarajuću vrijednost ciljne varijable Z.
6. Za probleme maksimizacije rješenje je točka u kojoj je Z maksimum; za probleme minimizacije rješenje je točka u kojoj je Z minimum.

TEMA: LINEARNO PROGRAMIRANJE

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

Pažnja!

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

Plaćanje. Kontakti.

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

- x 1 + 2 x 2 ≤ 2;

x 1 + 2 x 2 ≤ 10;

x i ≥ 0, i = 1,2.

Otopina:

Uvjetnom zamjenom znakova nejednakosti znakovima jednakosti dobivamo sustav jednadžbi x1 + x2 = 4;

- x1 + 2 x2 = 2;

x1 + 2 x2 = 10.

Konstruirajmo prave pravce pomoću ovih jednadžbi, zatim u skladu s predznacima nejednakosti izaberemo poluravnine i dobijemo njihov zajednički dio - područje dopustivih rješenja ODR-a - četverokut MNPQ.

Minimalna vrijednost funkcije

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

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

Maksimalna vrijednost se postiže u toč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

uz ograničenja: 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.

Otopina:

Uvjetnom zamjenom znakova nejednakosti znakovima jednakosti dobivamo sustav jednadžbi x1 - 4 x2 = 4 ;

3 x1 - x2 = 0;

Konstruirajmo pravce pomoću ovih jednadžbi, zatim, u skladu s predznacima nejednakosti, izaberemo poluravnine i dobijemo njihov zajednički dio - područje dopustivih rješenja ODR-a - neograničeni poligon MNPQ.

Minimalna vrijednost funkcije

cije – na izravnom NP-u, na primjer

u toč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

uz ograničenja: x 1 + 3 x 2 ≤ 18;

2 x 1 + x 2 ≤ 16;

x 2 ≤ 5;

x i ≥ 0, i = 1,2.

Uvjetnom zamjenom znakova nejednakosti znakovima jednakosti dobivamo sustav jednadžbi

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

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

3 x 1 = 21 (4).

Konstruirajmo prave pravce pomoću ovih jednadžbi, zatim u skladu s predznacima nejednakosti izaberemo poluravnine i dobijemo njihov zajednički dio - područje dopustivih rješenja ODR - poligona MNPQRS.

Konstruirajmo vektor G(2; -3) i provucimo ishodište koordinata linija razine- ravno.

Pomičemo liniju razine u smjeru, vrijednost F raste. U točki S(7; 0) funkcija cilja postiže maksimum F max =2·7–3·0= = 14. Pomičemo liniju razine u smjeru, vrijednost F opada. Minimalna vrijednost funkcije je u toč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

s 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.

Otopina:

Broj nepoznanica n=6, broj jednadžbi m=3. Stoga se r = n-m = 3 nepoznanice mogu uzeti kao slobodne. Izaberimo x 1, x 3 i x 6.

Izražavamo osnovne varijable x 2 , x 4 i x 5 preko slobodnih i svodimo sustav na jediničnu bazu

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

Funkcija cilja ć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 izvodljivo rješenje (0; 2; 0; 9; 6; 0), funkcija cilja F 1 = 13.

Varijable x 3 i x 6 uključene su u funkciju cilja s negativnim koeficijentima, stoga, kako se njihove vrijednosti povećavaju, vrijednost F će se smanjivati. Uzmimo x 6 za primjer. Iz 1. jednadžbe sustava (*) jasno je da je povećanje vrijednosti x 6 moguće do x 6 = 1 (dok je x 2 ³ 0). U tom 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. Dobivamo

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 slobodne varijable nulte vrijednosti, odnosno x 1 =x 2 = x 3 =0, dok je x 6 = 1, x 4 = 3, x 5 = 4, odnosno treće moguće rješenje (0; 0; 0; 3; 4; 1 ). U ovom slučaju F 3 = 6.

Varijabla x 3 uključena je u funkciju cilja s negativnim koeficijentom, stoga će povećanje x 3 u odnosu na nultu vrijednost dovesti do smanjenja F. Iz 2. jednadžbe jasno je da se x 3 može povećati na 1/4 , od 3. jednadžbe - do 2/3 . Druga jednadžba 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. Uhvatimo sustav

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

Funkcija cilja poprimit će 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 funkciju cilja s negativnim koeficijentima, stoga, kako se njihove vrijednosti povećavaju, vrijednost F će se smanjivati. Uzmimo za primjer x 2. Iz 2. jednadžbe sustava jasno je da je moguće povećanje vrijednosti x 2 do x 2 = 5 (dok je x 5 ³ 0). U ovom slučaju, x 1 i x 4 ostaju nula, vrijednosti ostalih varijabli jednake su 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. Uhvatimo sustav

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

Funkcija cilja poprimit će 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, stoga je daljnje 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

s 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;

Otopina:

Broj jednadžbi je 4, broj nepoznanica je 6. Dakle, r = n – m = 6 – 4 = 2 varijable se mogu izabrati kao slobodne varijable, 4 varijable kao osnovne. Kao slobodne odabiremo x 5 i x 6, a kao osnovne x 1 , x 2 , x 3 , x 4 . Izrazimo osnovne varijable preko slobodnih i svedimo sustav jednadžbi na jediničnu bazu

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;

Funkciju cilja 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 dobivamo 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 npr. x 6 u broj osnovnih. Iz jednadžbe (1) jasno je da je x 1 = 0 pri x 5 = 12, u (2) ÷ (4) x 6 uključeno s pozitivnim koeficijentima. Prijeđimo na novu osnovu: osnovne varijable - x 6, x 2, x 3, x 4, slobodne - 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 poprimit će 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 dobivamo drugo izvodljivo rješenje (0, 42 , 30, 21, 0, 12) i F 2 = 24.

Ciljna funkcija x 5 uključena je s pozitivnim koeficijentom, odnosno moguće je daljnje povećanje F. Prijeđ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 = 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 poprimit će 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 dobivamo treće moguće rješenje X 3 = (0, 0, 9, 7/2, 7, 5) i F 3 = 38.

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

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

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

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

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

Otopina:

Sustav jednadžbi-ograničenja je konzistentan, budući da su rangovi matrice sustava jednadžbi i proširene matrice isti i jednaki 2. Prema tome, dvije varijable se mogu uzeti kao slobodne, a druge dvije varijable - osnovne - mogu izraziti linearno kroz 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;

Funkcija cilja je već izražena kroz 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), s F 1 = 0.

Povećanje F moguće je povećanjem, na primjer, vrijednosti x 3, koja je uključena u izraz za F s pozitivnim koeficijentom (x 2 ostaje jednak nuli). Prva jednadžba sustava (*) pokazuje da se x 3 može povećati na 1 (iz uvjeta x 1 ³0), odnosno ova jednadžba nameće ograničenje na povećanje vrijednosti x 3. Prva jednadžba sustava (*) je razlučujuća. Na temelju ove jednadžbe, prelazimo na novu osnovu, mijenjajuć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 kroz x 1 i x 2.

Dobivamo: 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čavanjem slobodnih varijabli s nulom dobivamo drugo dopustivo osnovno rješenje X 2 = (0; 0; 1; 4), za koje je F 2 = 1.

Povećanje F moguće je s povećanjem x2. Uvećanje je x 2, sudeći prema najnoviji sustav jednadžbe (**), neograničeno. Posljedično, F će biti sve veći pozitivne vrijednosti, odnosno F max = + ¥.

Dakle, funkcija cilja F nije ograničena odozgo, stoga nema optimalnog rješenja.

ZADATAK 2.D. Sastavi dualni zadatak zadanom

izvorni problem.

Opcija 7. Maksimizirati funkciju cilja F = 2× x 1 - x 4

s 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)

Otopina:

Dovedimo sustav ograničenja u 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 funkciju cilja 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

s 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, (ja = 1, 6)

Otopina:

Imamo početni problem maksimiziranja sa sustavom ograničenja u obliku jednadžbi, to jest, par dualnih problema ima asimetrični tip 2 tipa, matematički model koji u matričnom obliku ima oblik:

Izvorni problem: Dvostruki problem:

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

kod A × X = B u A T × Y ≥ CT

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

matrica-stupac slobodnih članova i matrica koeficijenata za varijable u sustavu ograničenja imaju oblik

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

Nađimo transponiranu matricu koeficijenata, rednu matricu koeficijenata za varijable u funkciji cilja i matricu stupca slobodnih članova

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

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

Dualni problem bit će napisan u sljedećem obliku:

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

uz ograničenja 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

uz ograničenja: 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,

Otopina:

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

Izvorni problem Dvostruki problem

F = C × X min F = B T × Ymax

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

X ≥ 0 Y ≥ 0

U izvornom problemu matrica-red koeficijenata za varijable u funkciji cilja, matrica-stupac slobodnih članova i matrica koeficijenata za varijable u sustavu 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

Dualni problem je formuliran kao:

Maksimizirajte funkciju cilja 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 pomoću simpleks tablica.

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

s 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.

Otopina:

Dovedimo sustav 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 sustav od 3 jednadžbe sa 7 nepoznanica. Odaberimo 3 varijable x 1 , z 1 , z 3 kao osnovne, te x 2 , x 3 , x 4 , z 2 kao slobodne i kroz njih izrazimo osnovne varijable.

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

Zamijenimo u (1) i (3), dobivamo

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 simplex tablicu

I iteracija Tablica 1

Osnovno 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 Tablica 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 Tablica 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 Tablica 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.

U retku indeksa posljednji stol Ne negativni brojevi, odnosno u izrazu za funkciju cilja 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 funkciju cilja 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,

Otopina:

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 slobodnih varijabli, izrazimo osnovne varijable x 1, x 2 u terminima slobodnih i Reduciramo sustav na jediničnu bazu:

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

Napišimo sustav jednadžbi i funkciju cilja 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 = 10

Napravimo stol

I iteracija Tablica 1

Osnovno 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 Tablica 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 Tablica 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.

Ne postoji zadnja tablica u retku indeksa pozitivni brojevi, odnosno u izrazu za funkciju cilja sve G i > 0. Imamo slučaj I, dakle, zadnje osnovno rješenje je optimalno.

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

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

Opcija 10. Minimizirajte funkciju cilja F = x 1 + x 2,

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

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

Otopina:

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 jednadžbe sustava već su svedene na jediničnu bazu (osnovne varijable izražene su slobodnim), ali su napisane u obliku koji nije prikladan za korištenje simpleks tablica. Zapišimo sustav jednadžbi 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 slobodnim varijablama i pišemo je u obliku F - 3 x 3 +3 x 4 = 3

Napravimo stol

I iteracija Tablica 1

Osnovno 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.

Tablica 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 retku zadnje tablice nema pozitivnih brojeva, odnosno u izrazu za funkciju cilja sve Gi > 0. Imamo slučaj 1, dakle zadnje osnovno rješenje je optimalno.

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

Otopina: pronađite maksimalnu i minimalnu vrijednost funkcije \(f (x, y)\) pod sljedećim ograničenjima $$ f(x,y)=(x-4)^2 + (y-3)^2 \rightarrow max,min \ \\begin(cases) 2x+3y\geq 6 \\ 3x-2y\leq 18\\ -x+2y\leq 8\\ x,y\geq0\end(cases) $$
Grafička metoda Preporučljivo je koristiti rješenja zadataka za zadatke s dvije varijable, koji su napisani u simetričnom obliku, kao i za probleme s više varijabli, pod uvjetom da njihov kanonski zapis ne sadrži više od dvije slobodne varijable.

U u ovom slučaju problem s dvije varijable.

Algoritam za rješavanje problema “geometrijska interpretacija problema linearnog programiranja”:

1. Konstruirajmo područje izvedivih rješenja na xOy ravnini.
2. Istaknimo područje nenegativnih rješenja.

4. Konstruirajmo obitelj objektivnih funkcija.
5. Odredite najveću (minimalnu) vrijednost funkcije cilja.

1. Konstruirajte područje mogućih rješenja problema \(D\).

Za konstruiranje regije izvedivih rješenja:
1) Konstruirajte granične linije:
transformirajte nejednadžbe u jednakosti, a zatim u jednadžbu ravne linije u segmentima na osi oblika \(\frac(x)(a)+\frac(y)(b) = 1\), zatim \(x =a\) je segment odsječen na osi Ox, \(y=b\) - na osi Oy $$ \begin(cases) 2x+3y = 6 \\ 3x-2y = 18\\ -x+ 2y = 8 \end(cases) => \begin(cases) \frac(x)(3)+\frac(y)(2) = 1 \\ \frac(x)(8)-\frac(y) (9) = 1 \\ -\frac (x)(6)+ \frac(y)(4) = 1 \end(cases) $$ Za svaku ravnu liniju iscrtajte segmente na osi i povežite ih. Imamo potrebne ravne linije.

2) Odredite poluravnine koje zadovoljavaju zadane nejednakosti:
Jer nejednadžba \(2x+3y\geq 6\) je poluravnina koja leži iznad pravca \(2x+3y = 6\). Izravna klima
Jer nejednadžba \(3x-2y\leq 18 => -3x+2y \geq -18\) je poluravnina koja leži iznad pravca \(3x-2y = 18\). Ravni CB
Jer nejednadžba \(-x+2y\leq 8\) je poluravnina koja leži ispod ravne crte \(-x+2y = 8\). Ravna AB

Područje izvedivih rješenja definirano je kao opći dio tri poluravnine koje odgovaraju tim nejednakostima. Ovo područje je trokut \(ABC\)

Površina \(D\) je trokut \(ABC\) vidi sl.

2. Istaknimo područje nenegativnih rješenja.

Područje nenegativnih rješenja nalazi se u prvoj četvrtini i jest zajednički dio svih pet poluravnina, od kojih su tri područje \(D\), dobivene iz nejednadžbi i dodatno dvije nejednadžbe \(x \geq 0\) - gornja poluravnina (I i II četvrtina) i \(y \ geq 0\) - desna poluravnina (I i IV četvrtina), koje izražavaju uvjet nenegativnosti varijabli \(x;y\). Dobili smo traženo područje nenegativnih rješenja \(DEBFG\)

3. Odredite koordinate vrhova područja.
Koordinate četiri vrha su već poznate (to su točke sjecišta pravaca i osi).
Zapišimo ove koordinate:
\(D(0;2)\), \(E(0;4)\), \(F(6;0)\), \(G(3;0)\)
Nađimo koordinate točke \(B\) kao sjecišta pravaca \(-x+2y = 8\) i \(3x-2y = 18\). Riješimo sustav jednadžbi i pronađimo koordinate ove točke $$\begin(cases) -x+2y = 8\\ 3x-2y = 18\end(cases)=> \begin(cases) 2x = 26\\ 3x-2y = 18 \end(cases)=> \begin(cases) x = 13\\ y =10.5\end(cases)$$
Dobili smo koordinate točke \(B(13,10.5)\)

4. Konstruiramo familiju objektivnih funkcija.
Jednadžba \(f(x,y)=(x-4)^2 + (y-3)^2 \rightarrow max,min\) definira na ravnini xOy obitelj koncentričnih krugova sa središtem u točki s koordinate \(Q(4 ;3)\), od kojih svaka odgovara specifična vrijednost parametar \(f\). Kao što je poznato, za jednadžbu kruga parametar je \(f=R^2\).

Prikažimo u jednom koordinatnom sustavu familiju koncentričnih kružnica \(f\) i familiju ravnih linija. Zadatak određivanja najveće (minimalne) točke točke \(f\) svest će se na pronalaženje u važeće područje točka kroz koju prolazi krug obitelji \(f=const\) koja je odgovorna za najveću (najmanju) vrijednost parametra \(f\).

5. Odredite najveću (minimalnu) vrijednost funkcije cilja.

Minimalna vrijednost funkcije cilja: Autor postupno povećanje polumjera kružnice, ustanovili smo da je prvi vrh kroz koji kružnica prolazi točka \(G(3;0)\). Funkcija cilja u ovoj će točki biti minimalna i jednaka \(f(3,0)=(3-4)^2 + (0-3)^2 = 10\)

Maksimalna vrijednost funkcije cilja: Daljnjim povećanjem polumjera kruga, ustanovili smo da je posljednji vrh kroz koji će krug proći točka \(B(13;10.5)\). Funkcija cilja u ovoj će točki biti maksimalna i jednaka \(f(13,10,5)=(13-4)^2 + (10,5-3)^2 = 137,25\)

Točnost rješenja možete provjeriti zamjenom koordinata preostalih vrhova u jednadžbu funkcije cilja:
na vrhu \(D(0;2)\) vrijednost funkcije cilja je \(f(0,2)=(0-4)^2 + (2-3)^2 = 17\)
na vrhu \(E(0;4)\) vrijednost funkcije cilja je \(f(0,4)=(0-4)^2 + (4-3)^2 = 17\)
na vrhu \(F(6,0)\) vrijednost funkcije cilja je \(f(6,4)=(6-4)^2 + (0-3)^2 = 13\)
Kužim to

Odgovor:
minimalna vrijednost funkcije cilja \(f_(min) = 10\)
najveća vrijednost funkcije cilja \(f_(max) = 137,25\)

Grafičkom metodom pronađite maksimum funkcije cilja

F= 2x 1 + 3x 2 ® max

S ograničenjima

Otopina korištenjem Excel tablice

Prvo, napravimo ga na listu papira Excel rješenje sustavi nejednakosti.

Razmotrimo prvu nejednakost.

Konstruirajmo graničnu crtu pomoću dvije točke. Označavamo ravnu liniju (L1) (ili Red1). Koordinate X 2 izračunavamo pomoću formula:

Za konstrukciju odaberite raspršeni dijagram

Odabir podataka za izravni

Promijenite naziv retka:

Odabir izgleda grafikona. Promijenite naziv koordinatnih osi:

Ravna linija (L1) na grafikonu:

Rješenje stroge nejednakosti može se pronaći korištenjem jedne ispitne točke koja ne pripada liniji (L1). Na primjer, pomoću točke (0; 0)P(L1).

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

Nejednakost je istinita, stoga će rješenje nejednadžbe (1) biti poluravnina u kojoj se nalazi probna točka (na slici ispod linije L1).

Zatim rješavamo nejednadžbu (2).

Konstruirajmo graničnu liniju 2 koristeći dvije točke. Pravac označavamo s (L2).

Ravna linija (L2) na grafikonu:

Rješenje stroge nejednadžbe 2 može se pronaći pomoću jedne ispitne točke koja ne pripada liniji (L2). Na primjer, pomoću točke (0; 0)P(L2).

Zamjenom koordinata točke (0; 0) dobivamo nejednakost

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

Nejednakost je istinita, stoga će rješenje nejednadžbe (2) biti poluravnina u kojoj se nalazi probna točka (na slici ispod linije L2).

Zatim rješavamo nejednadžbu (3).

Konstruirajmo graničnu crtu pomoću dvije točke. Označavamo ravnu liniju (L3).

Ravna linija (L3) na grafikonu:

Rješenje stroge nejednadžbe 2 može se pronaći pomoću jedne ispitne točke koja ne pripada liniji (L3). Na primjer, pomoću točke (0; 0)P(L3).

Zamjenom koordinata točke (0; 0) dobivamo nejednakost

Nejednakost je točna, stoga će rješenje nejednadžbe (3) biti poluravnina u kojoj se nalazi probna točka (na slici ispod linije L3).

Zatim rješavamo nejednadžbu (4).

Konstruirajmo graničnu crtu pomoću dvije točke. Označavamo ravnu liniju (L4).

Dodajte podatke na Excel list

Ravna linija (L4) na grafikonu:

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

Zamjenom koordinata točke (0; 0) dobivamo nejednakost

Nejednakost je točna, stoga će rješenje nejednadžbe (4) biti poluravnina u kojoj se nalazi probna točka (na slici lijevo od pravca L4).

Rješavanjem dviju nejednadžbi (5) i (6)

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

Sustav nejednakosti je riješen. Rješavanjem sustava nejednadžbi (1) – (6) u u ovom primjeru je konveksni mnogokut u donjem lijevom kutu slike, omeđen pravcima L1, L2, L3, L4 i koordinatnim pravcima i . Možete se uvjeriti da je poligon ispravno odabran zamjenom ispitne točke, na primjer (1; 1), u svaku nejednadžbu izvornog sustava. Zamjenom točke (1; 1) nalazimo da su sve nejednakosti, uključujući i prirodna ograničenja, istinite.

Razmotrimo sada funkciju cilja

F= 2x 1 + 3x 2 .

Konstruirajmo linije razine za vrijednosti funkcije F=0 I F=12 (numeričke vrijednosti izabran slučajno). Dodajte podatke na Excel list

Linije razine na grafikonu:

Konstruirajmo vektor smjera (ili gradijent) (2; 3). Koordinate vektora podudaraju se s koeficijentima funkcije cilja F.