Optimalna vrijednost funkcije cilja naziva se. Testovi za tekuću provjeru znanja

Podijelimo treći red s ključnim elementom jednakim 5, dobivamo treći redak nove tablice.

Osnovni stupci odgovaraju pojedinačnim stupcima.

Izračun preostalih tabličnih vrijednosti:

"BP - Osnovni plan":

; ;

"x1": ; ;

"x5": ; .

Vrijednosti indeksnog reda su nenegativne, stoga dobivamo optimalno rješenje: , ; .

Odgovor: maksimalna dobit od prodaje proizvedenih proizvoda, jednaka 160/3 jedinica, osigurava se puštanjem samo proizvoda druge vrste u iznosu od 80/9 jedinica.

Zadatak broj 2

Zadan je problem nelinearnog programiranja. Grafoanalitičkom metodom pronađite maksimum i minimum funkcije cilja. Sastavite Lagrangeovu funkciju i pokažite da su dovoljni uvjeti minimuma (maksimuma) zadovoljeni u točkama ekstrema.

Jer zadnja znamenka šifre je 8, tada je A=2; B=5.

Jer pretposljednja znamenka šifre je 1, tada treba izabrati zadatak broj 1.

Riješenje:

1) Nacrtajmo površinu koju definira sustav nejednadžbi.

To područje je trokut ABC s koordinatama vrhova: A(0; 2); B(4; 6) i C(16/3; 14/3).

Razine ciljne funkcije su kružnice sa središtem u točki (2; 5). Kvadrati polumjera bit će vrijednosti funkcije cilja. Tada slika pokazuje da je minimalna vrijednost funkcije cilja postignuta u točki H, maksimalna vrijednost je ili u točki A ili u točki C.

Vrijednost funkcije cilja u točki A: ;

Vrijednost funkcije cilja u točki C: ;

To znači da je najveća vrijednost funkcije postignuta u točki A(0; 2) i jednaka je 13.

Nađimo koordinate točke H.

Da biste to učinili, razmotrite sustav:

ó

ó

Pravac je tangenta na kružnicu ako jednadžba ima jedinstveno rješenje. Kvadratna jednadžba ima jedinstveno rješenje ako je diskriminant 0.

Zatim ; ; - minimalna vrijednost funkcije.

2) Sastavite Lagrangeovu funkciju da biste pronašli minimalno rješenje:

Na x 1 =2.5; x 2 =4.5 dobivamo:

ó

Sustav ima rješenje za , tj. dovoljni uvjeti ekstrema su zadovoljeni.

Sastavljamo Lagrangeovu funkciju za pronalaženje maksimalnog rješenja:

Dovoljni uvjeti za ekstrem:

Na x 1 =0; x 2 =2 dobivamo:

ó ó

Sustav ima i rješenje, tj. dovoljni uvjeti ekstrema su zadovoljeni.

Odgovor: minimum funkcije cilja se postiže na ; ; maksimalna funkcija cilja se postiže kada ; .

Zadatak broj 3

Za dva poduzeća dodijeljena su sredstva u iznosu d jedinice. Kada se dodjeljuje prvom poduzeću na godinu dana x jedinicama fonda osigurava prihod k 1 x jedinice, a kada su raspoređeni na drugo poduzeće g jedinica fondova, osigurava prihod k 1 g jedinice. Stanje sredstava na kraju godine za prvo poduzeće je jednako nx, a za drugo moj. Kako raspodijeliti sva sredstva unutar 4 godine da ukupan prihod bude najveći? Riješite problem dinamičkim programiranjem.

i=8, k=1.

A=2200; k 1 =6; k2=1; n=0,2; m=0,5.

Riješenje:

Cijelo razdoblje od 4 godine podijeljeno je u 4 faze, od kojih je svaka jednaka jednoj godini. Nabrojimo faze počevši od prve godine. Neka su X k i Y k sredstva dodijeljena redom poduzećima A i B u k-toj fazi. Tada je zbroj X k + Y k =a k ukupan iznos sredstava korišten u k - toj fazi i preostalih od prethodne faze k - 1. u prvoj fazi se koriste sva dodijeljena sredstva i a 1 = 2200 jedinica. prihod koji će biti primljen u k - toj fazi, kada se X k i Y k jedinica dodijele, bit će 6X k + 1Y k . neka maksimalni dohodak primljen u posljednjim fazama počevši od k - ta faza je f k (a k) jedinica. Napišimo Bellmanovu funkcionalnu jednadžbu koja izražava načelo optimalnosti: bez obzira na početno stanje i početno rješenje, sljedeće rješenje mora biti optimalno u odnosu na stanje dobiveno kao rezultat početnog stanja:

Za svaki stupanj morate odabrati vrijednost X k i vrijednost Y k=ak- Xk. Imajući ovo na umu, pronaći ćemo prihod u k-toj fazi:

Funkcionalna Bellmanova jednadžba će izgledati ovako:

Razmotrite sve faze, počevši od posljednje.

(budući da je maksimum linearne funkcije postignut na kraju segmenta pri x 4 = a 4);

Konstruiramo na ravnini skup mogućih rješenja sustava linearnih nejednadžbi i geometrijski nalazimo minimalnu vrijednost funkcije cilja.

Gradimo u koordinatnom sustavu x 1 oh 2 linije

Nalazimo poluravnine određene sustavom. Kako su nejednakosti sustava zadovoljene za bilo koju točku iz 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.

Gradimo vektor i liniju nulte razine okomitu na njega.

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

Dakle, dobili smo poantu (13;11) i.

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

Dakle, dobili smo 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. Na jedan ormarić potroši se armatura za 10$, a na jedan stol 8$. Tvrtka od svojih dobavljača može dobiti do 600 m2 ploča mjesečno i pribor za 2000 dolara. Za svaki ormar potrebno je 7 sati strojnog rada, za stol 3 sata. Mjesečno je moguće koristiti samo 840 sati rada stroja.

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

• 1. Sastaviti matematički model problema i riješiti ga simpleks metodom.
• 2. Sastavite matematički model dualnog problema, zapišite 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 upotrebi svake vrste resursa.
• 5. Ocijenite izvedivost uvođenja nove vrste proizvoda - police za knjige, ako se za izradu jedne police potroši 1 m 2 ploča i pribora za 5 $, a potrebno je 0,25 sati rada stroja i dobit od prodaje jedna polica je 20 dolara.
• 1. Izgradimo matematički model za ovaj problem:

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

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

Zapišimo podatke zadatka u obliku tablice:

stol 1

Jer sada su sve delte veće od nule, tada je daljnje povećanje vrijednosti funkcije cilja f nemoguće i dobili smo optimalan plan.

Uvod

Suvremeni stadij razvoja čovječanstva razlikuje se po tome što stoljeće energetike smjenjuje doba informatike. Intenzivno se uvode nove tehnologije u sve sfere ljudskog djelovanja. Postoji realan problem tranzicije u informacijsko društvo, kojem bi razvoj obrazovanja trebao postati prioritet. Mijenja se i struktura znanja u društvu. Temeljna znanja koja pridonose kreativnom razvoju pojedinca postaju sve važnija za praktični život. Važna je i konstruktivnost stečenog znanja, sposobnost strukturiranja u skladu s ciljem. Na temelju znanja nastaju novi informacijski resursi društva. Formiranje i stjecanje novih znanja treba se temeljiti na strogoj metodologiji sustavnog pristupa, unutar kojega posebno mjesto zauzima modelski pristup. Mogućnosti pristupa modeliranju iznimno su raznolike kako u pogledu formalnih modela koji se koriste, tako iu načinu implementacije metoda modeliranja. Fizičko modeliranje omogućuje dobivanje pouzdanih rezultata za prilično jednostavne sustave.

Trenutačno je nemoguće imenovati područje ljudske aktivnosti u kojem se, u jednom ili drugom stupnju, ne bi koristile metode modeliranja. To se posebno odnosi na upravljanje različitim sustavima, gdje su glavni procesi donošenja odluka na temelju primljenih informacija.

1. Izjava problema

funkcija minimalnog cilja

Riješite problem nalaženja minimuma funkcije cilja za sustav ograničenja zadan poligonom odlučivanja prema opciji br. 16 zadatka. Poligon odluke prikazan je na slici 1:

Slika 1 - Poligon rješenja problema

Sustav ograničenja i ciljna funkcija problema prikazani su u nastavku:

Problem je potrebno riješiti pomoću sljedećih metoda:

Grafička metoda za rješavanje LP problema;

Algebarska metoda za rješavanje LP problema;

Simpleks metoda za rješavanje LP problema;

Metoda pronalaženja izvodljivog rješenja problema LP;

Rješavanje dualnog LP problema;

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

Gomoryjeva metoda za rješavanje cjelobrojnih LP problema;

Balashova metoda za rješavanje Booleovih LP problema.

Usporedite rezultate rješavanja različitim metodama kako biste donijeli 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 nepoznanica ne prelazi tri. Pogodan je za kvalitativno proučavanje svojstava rješenja i koristi se u kombinaciji s drugim metodama (algebarskim, grananjem i vezanjem, itd.). Ideja metode temelji se na grafičkom rješenju sustava linearnih nejednadžbi.

Riža. 2 Grafičko rješenje problema LP

Niska točka

Jednadžba pravca koji prolazi kroz dvije toč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)

s ograničenjima:

Rješavanje problema linearnog programiranja algebarskom simpleks metodom

Primjena algebarske metode za rješavanje problema zahtijeva generalizaciju prikaza problema LP. Izvorni sustav ograničenja zadan u obliku nejednakosti pretvara se u standardnu ​​notaciju kada su ograničenja zadana u obliku jednakosti. Pretvaranje sustava ograničenja u standardni oblik uključuje sljedeće korake:

Transformirajte nejednadžbe na način da varijable i slobodni članovi budu s lijeve strane, a 0 s desne strane, tj. da lijeva strana bude veća ili jednaka nuli;

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

Uvodeći dodatna ograničenja na nenegativnost dodanih varijabli, zamijeniti znakove nejednakosti znakovima striktnih jednakosti.

Kod rješavanja problema LP algebarskom metodom dodan je uvjet: funkcija cilja treba težiti minimumu. Ako ovaj uvjet nije zadovoljen, potrebno je na odgovarajući način transformirati funkciju cilja (pomnožiti s -1) i riješiti problem minimizacije. Nakon što je rješenje pronađeno, zamijenite vrijednosti varijabli u izvornoj funkciji i izračunajte njezinu vrijednost.

Rješenje problema pomoću algebarske metode smatra se optimalnim kada su vrijednosti svih osnovnih varijabli nenegativne, a koeficijenti slobodnih varijabli u jednadžbi ciljne funkcije također su nenegativni. Ako ovi uvjeti nisu ispunjeni, potrebno je transformirati sustav nejednakosti, izražavajući neke varijable kroz druge (mijenjajući slobodne i osnovne varijable) kako bi se postigla gornja ograničenja. Pretpostavlja se da je vrijednost svih slobodnih varijabli nula.

Algebarska metoda za rješavanje problema linearnog programiranja jedna je od najučinkovitijih metoda za ručno rješavanje problema malih dimenzija. ne zahtijeva veliki broj aritmetičkih izračuna. Strojna implementacija ove metode je kompliciranija nego, na primjer, za simpleks metodu, jer algoritam za rješavanje algebarskom metodom je u određenoj mjeri heuristički i učinkovitost rješenja uvelike ovisi o osobnom iskustvu.

slobodne varijable

lane St - dodati. komplet

Uvjeti nenegativnosti su zadovoljeni, stoga je pronađeno optimalno rješenje.

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

Rješenje: Dovedimo problem do standardnog oblika za rješavanje pomoću simpleks tablice.

Sve jednadžbe sustava svodimo na oblik:

Gradimo simpleks tablicu:

U gornji kut svake ćelije tablice upisujemo koeficijente iz sustava jednadžbi;

Odabiremo najveći pozitivni element u retku F, osim što će ovo biti opći stupac;

Da bismo pronašli opći element, gradimo relaciju za sve pozitivne. 3/3; 9/1;- minimalni omjer u retku x3. Dakle - opći niz i =3 - opći element.

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

U sve neispunjene donje kutove opće linije upisujemo umnožak vrijednosti u gornjem kutu ćelije s;

Odaberite gornje kutove opće linije;

U sve donje kutove općeg stupca upisujemo umnožak vrijednosti u gornjem kutu s - i odabiremo dobivene vrijednosti;

Preostale ćelije tablice popunjavaju se kao umnošci odgovarajućih odabranih elemenata;

Zatim gradimo novu tablicu u kojoj su oznake ćelija elemenata općeg stupca i retka obrnute (x2 i x3);

U gornjem kutu bivšeg općeg retka i stupca ispisane su vrijednosti koje su prethodno bile u donjem kutu;

Zbroj vrijednosti gornjih i donjih kutova ovih ćelija u prethodnoj tablici zapisan je u gornjem kutu preostalih ćelija

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

Neka je dan sustav linearnih algebarskih jednadžbi:

Možemo pretpostaviti da sve, inače množimo odgovarajuću jednadžbu s -1.

Uvodimo pomoćne varijable:

Uvodimo i pomoćnu funkciju

Sustav ćemo minimizirati pod ograničenjima (2) i uvjetima.

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

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

min f=0, tada svi i moraju biti jednaki nuli. A dobivene vrijednosti xj bit će izvedivo rješenje za sustav (1).

min f>0, tj. izvorni sustav nema valjano rješenje.

Izvorni sustav:

Koristi se uvjet problema iz prethodne teme.

Dodajmo dodatne varijable:

Nađeno je prihvatljivo rješenje izvornog zadatka: x1 = 3, x2 = 3, F = -12. Na temelju dobivenog izvodljivog rješenja pronalazimo optimalno rješenje izvornog problema koristeći simpleks metodu. Da bismo to učinili, izgradit ćemo novu simpleks tablicu iz gornje tablice brisanjem retka i retka s ciljnom funkcijom pomoćnog zadatka:

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

6. Dvojni problem linearnog programiranja

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

s ograničenjima:

Rješenje: Sustav ograničenja dovodimo u standardnu ​​formu:

Dualni zadatak ovom izgledat će ovako:

Dualni problem će se riješiti simpleks metodom.

Transformirajmo funkciju cilja tako da problem minimizacije bude riješen i zapišimo sustav ograničenja u standardnom obliku za rješavanje simpleks metodom.

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

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

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

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

Drugi korak simpleks metode

Dakle, u trećem koraku simpleks metode pronađeno je optimalno rješenje problema minimizacije sa sljedećim rezultatima: y2 = -7 /8, y1 = -11/8, F = 12. Da bismo pronašli vrijednost funkciju cilja dualnog problema, zamjenjujemo pronađene vrijednosti osnovne i slobodne varijable u funkciju maksimizacije:

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

Budući da je vrijednost funkcije cilja izravnog i dualnog zadatka ista, rješenje izravnog zadatka je pronađeno i jednako je 12.

Fmin \u003d Fmax \u003d -12

7. Rješavanje problema cjelobrojnog linearnog programiranja metodom “grananja i granica”.

Transformirajmo izvorni problem na način da cjelobrojni uvjet nije zadovoljen pri rješavanju konvencionalnim metodama.

Početni poligon rješenja problema cjelobrojnog programiranja.

Konstruirajmo novi sustav ograničenja za transformirani poligon rješenja.

Zapisujemo sustav ograničenja u obliku jednakosti, za rješavanje algebarskom metodom.

Kao rezultat rješenja nađen je optimalni plan zadatka: x1 = 9/4, x2 = 5/2, F = -41/4. Ovo rješenje ne zadovoljava uvjet integralnosti postavljen u problemu. Poligon originalnog rješenja dijelimo na dvije regije, isključujući regiju 3 iz nje

Promijenjen poligon rješenja problema

Sastavimo nove sustave ograničenja za formirana područja poligona rješenja. Lijevo područje je četverokut (trapez). Sustav ograničenja za lijevo područje poligona rješenja prikazan je u nastavku.

Sustav ograničenja za lijevu regiju

Desno područje predstavlja točku C.

Sustav ograničenja za područje ispravne odluke prikazan je u nastavku.

Novi sustavi ograničenja su dva sporedna problema koja se trebaju riješiti neovisno jedan o drugom. Riješimo problem cjelobrojnog programiranja za lijevu regiju poligona rješenja.

Kao rezultat rješenja nađ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 izvorni problem cjelobrojnog linearnog programiranja. Nema smisla provoditi rješenje za pravo područje rješenja. Slika ispod prikazuje napredak rješavanja problema cjelobrojnog linearnog programiranja u obliku stabla.

Tečaj rješavanja problema cjelobrojnog linearnog programiranja metodom Gomory.

U mnogim praktičnim primjenama od velikog je interesa problem cjelobrojnog programiranja, u kojem su zadani sustav linearnih nejednadžbi i linearni oblik

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

Jednu od metoda za rješavanje problema cjelobrojnog programiranja predložio je Gomory. Ideja metode je korištenje metoda kontinuiranog linearnog programiranja, posebno simpleksne metode.

1) Simpleks metodom utvrđuje se rješenje problema (1), (2) za koje se uklanja zahtjev da rješenje bude cjelobrojno; ako se rješenje pokaže cjelobrojnim, tada će se pronaći i željeno rješenje cjelobrojnog problema;

2) U protivnom, ako neka koordinata nije cijeli broj, dobiveno rješenje zadatka provjerava se na mogućnost postojanja cjelobrojnog rješenja (prisutnost cjelobrojnih točaka u dopustivom poliedru):

ako se u bilo kojem retku s frakcijskim slobodnim članom svi ostali koeficijenti pokažu cijelim brojevima, tada nema cijelih brojeva, točaka u dopustivom poliedru, i problem cjelobrojnog programiranja nema rješenja;

U protivnom se uvodi dodatno linearno ograničenje koje od dopustivog poliedra odsijeca dio koji nije perspektivan za pronalaženje rješenja problema cjelobrojnog programiranja;

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

gdje su i razlomački dijelovi koeficijenata i slobodnih

član. Uvedimo pomoćnu varijablu u ograničenje (3):

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

gdje su i najbliži niži cijeli brojevi za i, redom.

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

Rješenje: Svodimo sustav linearnih ograničenja i funkciju cilja na kanonski oblik:

Odredimo optimalno rješenje sustava linearnih ograničenja, privremeno odbacujući cjelobrojni uvjet. Za to koristimo simpleks metodu. Donje tablice redom prikazuju početno rješenje problema, a dane su transformacije izvorne tablice kako bi se dobilo optimalno rješenje problema:

Rješavanje Booleovih LP problema Balashevom metodom.

Sastavite svoju varijantu za problem cjelobrojnog linearnog programiranja s Booleovim varijablama, vodeći računa o sljedećim pravilima: problem koristi najmanje 5 varijabli, najmanje 4 ograničenja, koeficijenti ograničenja i funkcija cilja biraju se proizvoljno, ali u takvom način na koji je sustav ograničenja kompatibilan. Zadatak je riješiti ZCLP s Booleovim varijablama korištenjem Balashovog algoritma i odrediti smanjenje računske složenosti u odnosu na rješavanje problema iscrpnim pretraživanjem.

Izvršenje ograničenja

F vrijednost

Ograničenje filtra:

Izračun Smanjenje Određivanje

Rješenje zadatka metodom iscrpne pretrage je 6*25=192 izračunata 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 projektiranja informacijskih sustava koji implementiraju nove informacijske tehnologije stalno se unapređuje. Sve složeniji sustavi postaju središte pažnje sistemskih inženjera, što otežava korištenje fizičkih modela i povećava važnost matematičkih modela i računalne simulacije sustava. Strojno modeliranje postalo je učinkovit alat za istraživanje i projektiranje složenih sustava. Relevantnost matematičkih modela u stalnom je porastu zbog njihove fleksibilnosti, primjerenosti stvarnim procesima, niske cijene implementacije na temelju suvremenih osobnih računala. Sve više mogućnosti pruža se korisniku, odnosno stručnjaku za modeliranje sustava pomoću računalne tehnologije. Korištenje modeliranja posebno je učinkovito u ranim fazama projektiranja automatiziranih sustava, kada je trošak pogrešnih odluka najveći.

Suvremeni računalni alati omogućili su značajno povećanje složenosti modela koji se koriste u proučavanju sustava, postalo je moguće izgraditi kombinirane, analitičke i simulacijske modele koji uzimaju u obzir cijeli niz čimbenika koji se odvijaju u stvarnim sustavima, tj. korištenje modela koji su adekvatniji fenomenima koji se proučavaju.

Književnost:

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

2. Smjernice za provedbu projekta kolegija u disciplini "Primijenjena matematika" za studente specijalnosti "Računalni sustavi i mreže" s punim radnim vremenom i izvanrednim oblicima obrazovanja / Sastavili: I.A. Balakireva, A.V. Skatkov - Sevastopol: Izdavačka kuća SevNTU , 2003. - 15 str.

3. Upute za studij discipline "Primijenjena matematika", odjeljak "Metode globalnog pretraživanja i jednodimenzionalne minimizacije" / Komp. A. V. Skatkov, I. A. Balakireva, L. A. Litvinova - Sevastopolj: Izdavačka kuća SevGTU, 2000. - 31s.

4. Smjernice za proučavanje discipline "Primijenjena matematika" za studente specijalnosti "Računalni sustavi i mreže" Odsjek "Rješavanje problema cjelobrojnog linearnog programiranja" redovnih i dopisnih oblika obrazovanja / Sastavili: I.A. Balakireva, A.V. Skatkov - Sevastopol : Izdavačka kuća SevNTU, 2000. - 13 str.

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

6. Proc. dodatak za učeničko gospodarstvo. specijalista. sveučilišta.-M.: Viš. škola, 1986.- 319s., ilustr.

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

Slični dokumenti

Algoritam za rješavanje problema linearnog programiranja simpleks metodom. Konstrukcija 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 s umjetnom osnovom problema kanonskog linearnog programiranja. Provjera optimalnosti rješenja.

test, dodan 05.04.2016


Teorijske osnove linearnog programiranja. Problemi linearnog programiranja, metode rješavanja. Analiza optimalnog rješenja. Rješenje problema jednoindeksnog linearnog programiranja. Izjava problema i unos podataka. Koraci izrade modela i rješenja.

seminarski rad, dodan 09.12.2008


Konstrukcija matematičkog modela. Izbor, obrazloženje i opis metode za rješavanje izravnog problema linearnog programiranja simpleks metodom, koristeći simpleks tablicu. Formulacija i rješenje dualnog problema. Analiza modela na osjetljivost.

seminarski rad, dodan 31.10.2014


Izrada matematičkog modela kako bi se maksimizirao profit poduzeća, grafičko rješenje problema. Rješavanje problema pomoću dodatka SOLVER. Analiza promjena rezervi sirovina. 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 provjera u MS Excelu. Analiza unutarnje strukture rješenja problema u programu. Optimizacija plana proizvodnje. Rješenje problema simpleks metodom. Višekanalni sustav čekanja.

test, dodan 02.05.2012


Rješavanje problema linearnog programiranja simpleks metodom: postavljanje problema, izgradnja ekonomsko-matematičkog modela. Rješenje prometnog problema metodom potencijala: izrada početnog referentnog plana, određivanje njegove optimalne vrijednosti.

test, dodan 04/11/2012


Postavka problema nelinearnog programiranja. Određivanje stacionarnih točaka i njihove vrste. Konstrukcija linija razine, trodimenzionalni graf funkcije cilja i ograničenja. Grafičko i analitičko rješenje problema. Korisnički priručnik i shema algoritma.

seminarski rad, dodan 17.12.2012


Analiza rješenja problema linearnog programiranja. Simpleksna metoda pomoću simpleksnih tablica. Modeliranje i rješavanje LP problema na računalu. Ekonomska interpretacija optimalnog rješenja problema. Matematička formulacija transportnog problema.

Ako postoje samo dvije varijable u problemu linearnog programiranja, tada se on može riješiti grafički.

Razmotrimo problem linearnog programiranja s dvije varijable i:
(1.1) ;
(1.2)
Ovdje su proizvoljni brojevi. Zadatak može biti i pronaći maksimum (max) i pronaći minimum (min). U sustavu ograničenja mogu biti prisutni i znakovi i znakovi.

Konstrukcija domene izvedivih rješenja

Grafička metoda za rješavanje problema (1) je sljedeća.
Prvo crtamo koordinatne osi i odabiremo mjerilo. Svaka od nejednakosti sustava ograničenja (1.2) definira poluravninu omeđenu odgovarajućim pravcem.

Dakle, prva nejednakost
(1.2.1)
definira poluravninu omeđenu pravcem. S jedne strane ove linije, a s druge strane. Na najravnijoj liniji. Da bismo saznali s koje je strane nejednakost (1.2.1) zadovoljena, odaberemo proizvoljnu točku koja ne leži na pravcu. Zatim zamijenimo koordinate ove točke u (1.2.1). Ako nejednakost vrijedi, tada poluravnina sadrži odabranu točku. Ako nejednakost nije zadovoljena, tada se poluravnina nalazi s druge strane (ne sadrži odabranu točku). Osjenčaj poluravninu za koju vrijedi nejednakost (1.2.1).

Isto činimo i za preostale nejednakosti sustava (1.2). Tako dobivamo osjenčane poluravnine. Točke domene dopustivih rješenja zadovoljavaju sve nejednadžbe (1.2). Dakle, grafički, područje izvodljivih rješenja (ODD) je sjecište svih izgrađenih poluravnina. Sjenčamo ODR. To je konveksni mnogokut čija lica pripadaju konstruiranim linijama. Također, ODR može biti neograničena konveksna figura, segment, zraka ili ravna linija.

Također se može dogoditi da poluravnine nemaju zajedničkih točaka. Tada je domena dopustivih rješenja prazan skup. Ovaj problem nema rješenja.

Možete pojednostaviti metodu. Ne možete zasjeniti svaku poluravninu, već prvo izgraditi sve linije
(2)
Zatim odaberite proizvoljnu točku koja ne pripada nijednom od ovih pravaca. Zamijenite koordinate te točke u sustav nejednadžbi (1.2). Ako su sve nejednakosti zadovoljene, tada je područje mogućih rješenja ograničeno konstruiranim linijama i uključuje odabranu točku. Osjenčamo područje dopuštenih rješenja duž granica linija tako da uključuje odabranu točku.

Ako barem jedna nejednakost nije zadovoljena, odaberite drugu točku. I tako dalje, dok se ne nađe jedna točka čije koordinate zadovoljavaju sustav (1.2).

Pronalaženje ekstrema funkcije cilja

Dakle, imamo osjenčanu regiju izvedivih rješenja (ODR). Omeđena je izlomljenom linijom koja se sastoji od odsječaka i zraka koje pripadaju konstruiranim pravcima (2). ODR je uvijek konveksan skup. To može biti ili ograničen skup ili neograničen skup duž nekih pravaca.

Sada možemo tražiti ekstrem funkcije cilja
(1.1) .

Da biste to učinili, odaberite bilo koji broj i izgradite ravnu liniju
(3) .
Radi lakšeg daljnjeg prikaza, pretpostavljamo da ova ravna linija prolazi kroz ODS. Na ovoj ravnoj liniji funkcija cilja je konstantna i jednaka . takav se pravac naziva linija razine funkcije. Taj pravac dijeli ravninu na dvije poluravnine. Na jednoj poluravni
.
Na drugoj polovici ravnine
.
To jest, s jedne strane ravne linije (3), funkcija cilja raste. I što više odmičemo točku od pravca (3), vrijednost će biti veća. S druge strane pravca (3) funkcija cilja opada. I što više odmičemo točku od linije (3) na drugu stranu, vrijednost će biti manja. Ako nacrtamo liniju paralelnu s linijom (3), tada će nova linija također biti linija razine ciljne funkcije, ali s drugom vrijednošću.

Dakle, da bi se našla maksimalna vrijednost funkcije cilja, potrebno je nacrtati ravnu liniju paralelnu s ravnom linijom (3), što je dalje moguće od nje u smjeru rastućih vrijednosti , i prolazi kroz barem jednu točku ODT-a. Za pronalaženje minimalne vrijednosti funkcije cilja potrebno je povući ravnu liniju paralelnu s pravom linijom (3) i što dalje od nje u smjeru pada vrijednosti , a koja prolazi kroz barem jednu točku od ODT-a.

Ako je ODE neograničen, tada se može pojaviti slučaj kada se takva ravna linija ne može povući. Odnosno, kako god ravnu liniju udaljili od linije razine (3) u smjeru porasta (smanjenja), ravna će uvijek prolaziti kroz ODR. U ovom slučaju može biti proizvoljno velika (mala). Stoga ne postoji maksimalna (minimalna) vrijednost. Problem nema rješenja.

Promotrimo slučaj kada krajnji pravac paralelan s proizvoljnim pravcem oblika (3) prolazi kroz jedan vrh ODD poligona. Iz grafa odredimo koordinate tog vrha. Tada se najveća (minimalna) vrijednost funkcije cilja određuje formulom:
.
Rješenje problema je
.

Također može postojati slučaj kada je ravna linija paralelna s jednom od strana ODS-a. Tada pravac prolazi kroz dva vrha ODD poligona. Odredimo koordinate tih vrhova. Da biste odredili najveću (minimalnu) vrijednost funkcije cilja, možete koristiti koordinate bilo kojeg od ovih vrhova:
.
Problem ima beskonačno mnogo rješenja. Rješenje je bilo koja točka koja se nalazi na segmentu između točaka i , uključujući same točke i .

Primjer rješavanja problema linearnog programiranja grafičkom metodom

Zadatak

Tvrtka proizvodi haljine dva modela A i B. Koriste se tri vrste tkanina. Za izradu jednog modela A haljine potrebno je 2 m tkanine prve vrste, 1 m tkanine druge vrste, 2 m tkanine treće vrste. Za izradu jedne haljine modela B potrebno je 3 m tkanine prve vrste, 1 m tkanine druge vrste, 2 m tkanine treće vrste. Zalihe tkanine prve vrste su 21 m, druge vrste - 10 m, treće vrste - 16 m. Puštanje jednog proizvoda tipa A donosi prihod od 400 den. jedinica, jedan proizvod tipa B - 300 den. jedinice

Napravite plan proizvodnje koji će poduzeću osigurati najveći prihod. Riješi zadatak grafički.

Riješenje

Neka varijable i označavaju broj proizvedenih haljina modela A odnosno B. Tada će količina upotrijebljenog tkiva prve vrste biti:
(m)
Količina tkanine koja se koristi za drugu vrstu bit će:
(m)
Količina tkanine koja se koristi za treću vrstu bit će:
(m)
Budući da broj proizvedenih haljina ne može biti negativan, dakle
i .
Prihod od proizvedenih haljina bit će:
(den. jedinice)

Tada ekonomsko-matematički model problema ima oblik:

Rješavamo ga grafički.
Nacrtajte koordinatne osi i .

Gradimo ravnu liniju.
U .
U .
Kroz točke (0; 7) i (10,5; 0) povučemo ravnu liniju.

Gradimo ravnu liniju.
U .
U .
Kroz točke (0; 10) i (10; 0) povučemo ravnu liniju.

Gradimo ravnu liniju.
U .
U .
Kroz točke (0; 8) i (8; 0) povučemo ravnu liniju.

Područje osjenčamo tako da točka (2; 2) padne u osjenčani dio. Dobivamo četverokut OABC.

(P1.1) .
U .
U .
Kroz točke (0; 4) i (3; 0) povučemo ravnu liniju.

Nadalje, primjećujemo da budući da su koeficijenti pri i funkcije cilja pozitivni (400 i 300), onda ona raste s povećanjem i . Povučemo pravac paralelan s pravcem (A1.1), što dalje od njega u smjeru povećanja, a prolazi kroz barem jednu točku četverokuta OABC. Takav pravac prolazi točkom C. Iz konstrukcije odredimo njegove koordinate.
.

Rješenje problema: ;

Odgovor

.
Odnosno, da biste dobili najveći prihod, potrebno je napraviti 8 haljina modela A. Prihod će u ovom slučaju biti 3200 den. jedinice

Primjer 2

Zadatak

Riješite problem linearnog programiranja grafičkom metodom.

Riješenje

Rješavamo ga grafički.
Nacrtajte koordinatne osi i .

Gradimo ravnu liniju.
U .
U .
Kroz točke (0; 6) i (6; 0) povučemo ravnu liniju.

Gradimo ravnu liniju.
Odavde.
U .
U .
Kroz točke (3; 0) i (7; 2) povučemo ravnu liniju.

Gradimo ravnu liniju.
Gradimo ravnu liniju (os apscisa).

Domena dopustivih rješenja (DDR) ograničena je konstruiranim ravnim linijama. Da bismo saznali s koje strane, uočavamo da točka pripada ODT jer zadovoljava sustav nejednakosti:

Područje duž granica izgrađenih linija osjenčamo tako da točka (4; 1) padne u osjenčani dio. Dobili smo trokut ABC.

Konstruiramo proizvoljnu liniju razine funkcije cilja, na primjer,
.
U .
U .
Kroz točke (0; 6) i (4; 0) povučemo ravnu nivelaciju.
Budući da ciljna funkcija raste s porastom i , povlačimo ravnu crtu paralelnu s ravninom i što dalje od nje u smjeru povećanja , a prolazi kroz barem jednu točku trokuta ABC. Takav pravac prolazi točkom C. Iz konstrukcije odredimo njegove koordinate.
.

Rješenje problema: ;

Odgovor

Primjer bez rješenja

Zadatak

Grafički riješiti problem linearnog programiranja. Nađite najveću i najmanju vrijednost funkcije cilja.

Riješenje

Zadatak rješavamo grafički.
Nacrtajte koordinatne osi i .

Gradimo ravnu liniju.
U .
U .
Kroz točke (0; 8) i (2.667; 0) povučemo ravnu liniju.

Gradimo ravnu liniju.
U .
U .
Kroz točke (0; 3) i (6; 0) povučemo ravnu liniju.

Gradimo ravnu liniju.
U .
U .
Kroz točke (3; 0) i (6; 3) povučemo ravnu liniju.

Pravci i su koordinatne osi.

Područje dopustivih rješenja (SDR) ograničeno je konstruiranim ravnima i koordinatnim osima. Da bismo saznali s koje strane, uočavamo da točka pripada ODT jer zadovoljava sustav nejednakosti:

Osjenčamo područje tako da točka (3; 3) padne u osjenčani dio. Dobivamo neograničeno područje omeđeno izlomljenom linijom ABCDE.

Konstruiramo proizvoljnu liniju razine funkcije cilja, na primjer,
(P3.1) .
U .
U .
Kroz točke (0; 7) i (7; 0) povučemo ravnu liniju.
Budući da su koeficijenti pri i pozitivni, tada raste s povećanjem i .

Da biste pronašli maksimum, morate nacrtati paralelnu liniju, što je više moguće u smjeru povećanja, a koja prolazi kroz barem jednu točku područja ABCDE. Međutim, budući da je područje neograničeno na strani velikih vrijednosti i , takva se ravna linija ne može povući. Koju god ravnu liniju nacrtali, uvijek će postojati točke u regiji koje su udaljenije u smjeru povećanja i . Stoga ne postoji maksimum. možete ga učiniti velikim koliko želite.

Tražimo minimum. Nacrtamo ravnu liniju paralelnu s pravcem (A3.1) i što dalje od nje u smjeru pada , a prolazi kroz barem jednu točku područja ABCDE. Takav pravac prolazi točkom C. Iz konstrukcije odredimo njegove koordinate.
.
Minimalna vrijednost funkcije cilja:

Odgovor

Ne postoji najveća vrijednost.
Minimalna vrijednost
.