Nađi grafička metoda maksimum ciljna funkcija

F= 2x 1 + 3x 2 ® max

Uz ograničenja

Rješenje korišćenjem 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 poluravan 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šavanjem sistema nejednačina (1) - (6) in ovaj primjer 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 odabrano 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.

Konstruirajmo na ravni skup dopuštenih rješenja sistema linearne nejednakosti i geometrijski pronaći minimalna vrijednost ciljna funkcija.

Ugrađujemo u koordinatni sistem x 1 oh 2 linije

Nalazimo poluravnine određene sistemom. Pošto su nejednakosti sistema zadovoljene za bilo koju tačku iz odgovarajuće poluravni, dovoljno ih je provjeriti za bilo koju tačku. Koristimo tačku (0;0). Zamenimo njegove koordinate u prvu nejednakost sistema. Jer , tada nejednakost definira poluravninu koja ne sadrži tačku (0;0). Slično, definiramo preostale poluravnine. Skup izvodljivih rješenja nalazimo kao opšti dio rezultujuće poluravnine je zasjenjeno područje.

Gradimo vektor i liniju nultog nivoa okomitu na njega.

Pomeranjem prave (5) u pravcu vektora vidimo da će maksimalna tačka regiona biti u tački A preseka prave (3) i prave (2). Nalazimo rješenje sistema jednačina:

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

Pomeranjem prave (5) u pravcu vektora vidimo da će minimalna tačka regiona biti u tački B preseka prave (1) i prave (4). Nalazimo rješenje sistema jednačina:

Dakle, dobili smo poen (6;6) i.

2. Firma za namještaj proizvodi kombinovane ormare i kompjuterske stolove. Njihova proizvodnja je ograničena dostupnošću sirovina (kvalitetne ploče, okovi) i vremenom rada mašina koje ih obrađuju. Za svaki ormar je potrebno 5 m2 dasaka, za sto - 2 m2. Oprema za 10$ se troši na jedan ormarić, a 8$ na jedan sto. Kompanija može dobiti od svojih dobavljača do 600 m2 ploča mjesečno i pribora za 2000 USD. Za svaki ormar potrebno je 7 sati mašinskog rada, za sto - 3 sata. Mjesečno je moguće koristiti samo 840 sati rada mašine.

Koliko kombinovanih ormara i kompjuterskih stolova bi firma trebalo da proizvede mesečno da bi maksimizirala profit ako jedan kabinet donosi 100 dolara, a svaki sto zarađuje 50 dolara?

• 1. Compose matematički model problem i riješi ga jednostavnim metodom.
• 2. Napravite matematički model dvostruki zadaci i zapiši njegovo rješenje na osnovu rješenja originalnog.
• 3. Odrediti stepen oskudice korišćenih resursa i opravdati isplativost optimalnog plana.
• 4. Istražite mogućnosti daljeg povećanja učinka, u zavisnosti od upotrebe svake vrste resursa.
• 5. Procijeniti izvodljivost uvođenja nove vrste proizvoda - police za knjige, ako se 1 m 2 dasaka i pribora za 5 dolara potroši na izradu jedne police, a potrebno je 0,25 sati rada mašine i dobit od prodaje jedne police je 20 dolara.
• 1. Napravimo matematički model za ovaj problem:

Označiti sa x 1 - obim proizvodnje ormara, a x 2 - obim proizvodnje stolova. Hajde da sastavimo sistem ograničenja i ciljnu funkciju:

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

Zapišimo podatke zadatka u obliku tabele:

Tabela 1

Jer sada je sve delta Iznad nule, onda je daljnje povećanje vrijednosti ciljne funkcije f nemoguće i dobili smo optimalan plan.

Uvod

Moderna faza ljudskog razvoja je drugačija po tome što se vijek energije zamjenjuje dobom informatike. Intenzivno se uvode nove tehnologije u svim oblastima ljudska aktivnost. Ustaje pravi problem prelazak na informaciono društvo, za koji razvoj obrazovanja treba da postane prioritet. Struktura znanja u društvu se također mijenja. Sve veća vrijednost za praktičan život steknu osnovna znanja koja doprinose kreativni razvoj ličnost. Važna je i konstruktivnost stečenog znanja, sposobnost njegovog strukturiranja u skladu sa ciljem. Na osnovu znanja, novo informacionih resursa društvo. Formiranje i sticanje novih znanja treba da se zasniva na strogoj metodologiji sistemski pristup, u okviru koje posebno mjesto 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 se posebno odnosi na oblast upravljanja. razni sistemi, gdje 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 problemi 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 pogled 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;

Ulazak dodatna ograničenja o nenegativnosti dodatih varijabli, zamijeniti znakove nejednakosti znakovima strogih jednakosti.

Prilikom rješavanja LP problema algebarska metoda dodaje se uslov: funkcija cilja mora težiti minimumu. Ako ovaj uvjet nije ispunjen, 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čkim proračunima. 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, dakle, našli smo optimalno reš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:

AT gornji ugao za svaku ćeliju tabele unosimo 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 sve, inače se množimo odgovarajuća jednačina od -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 prihvatljivo rešenje sistemi (1).

min f>0, tj. originalni sistem nema izvodljivo 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”.

Hajde da se transformišemo originalni problem na način da pri rješavanju konvencionalnim metodama nije 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 regiju

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 od velikog je interesa problem cjelobrojnog programiranja, 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.

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

1) 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 centru 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.

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, na 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. Idemo po 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 dodjeljujemo 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. Prema tome, 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čan oblik 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).

Treći red podijelimo ključnim elementom jednakim 5, dobićemo treći red nove tabele.

Osnovni stupci odgovaraju pojedinačnim stupcima.

Izračun preostalih vrijednosti u tabeli:

"BP - Osnovni plan":

; ;

"x1": ; ;

"x5": ; .

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

odgovor: maksimalni profit od prodaje proizvedenih proizvoda, jednak 160/3 jedinica, osiguran je oslobađanjem samo proizvoda druge vrste u iznosu od 80/9 jedinica.

Zadatak broj 2

Dat je problem nelinearnog programiranja. Odredite maksimum i minimum funkcije cilja koristeći grafsko-analitičku metodu. Sastavite Lagrangeovu funkciju i pokažite je na tačkama ekstrema dovoljne uslove minimum (maksimum).

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

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

Rješenje:

1) Nacrtajmo površinu koju definiše sistem nejednakosti.

Ovo područje je trougao ABC sa koordinatama vrhova: A(0; 2); B(4; 6) i C(16/3; 14/3).

Nivoi funkcije cilja su kružnice sa centrom u tački (2; 5). Kvadrati radijusa bit će vrijednosti ciljne funkcije. Tada slika pokazuje da je minimalna vrijednost ciljne funkcije postignuta u tački H, a maksimalna vrijednost je ili u tački A ili u tački C.

Vrijednost ciljne funkcije u tački A: ;

Vrijednost ciljne funkcije u tački C: ;

To znači da je maksimalna vrijednost funkcije dostignuta u tački A(0; 2) i jednaka je 13.

Nađimo koordinate tačke H.

Da biste to učinili, razmotrite sistem:

ó

ó

Prava je tangenta na kružnicu ako jednačina ima jedinstveno rješenje. Kvadratna jednadžba ima jedinstveno rješenje ako je diskriminanta 0.

Onda ; ; - minimalna vrijednost funkcije.

2) Sastavite Lagrangeovu funkciju da pronađete minimalno rješenje:

At x 1 =2.5; x 2 =4.5 dobijamo:

ó

Sistem ima rješenje za , tj. dovoljni ekstremni uslovi su zadovoljeni.

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

Dovoljni uslovi za ekstrem:

At x 1 =0; x 2 =2 dobijamo:

ó ó

Sistem takođe ima rešenje, tj. dovoljni ekstremni uslovi su zadovoljeni.

odgovor: minimum funkcije cilja je dostignut na ; ; maksimalna funkcija cilja se postiže kada ; .

Zadatak broj 3

Za dva preduzeća su dodijeljena sredstva u iznosu d jedinice. Kada se dodjeljuje prvom preduzeću na godinu dana x jedinice sredstava koje obezbjeđuje prihod k 1 x jedinice, i kada se dodjeljuju drugom preduzeću y jedinicama sredstava, ona daje prihod k 1 y jedinice. Stanje sredstava na kraju godine za prvo preduzeće je jednako nx, a za drugi moj. Kako rasporediti sva sredstva u roku od 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.

Rješenje:

Cijeli period od 4 godine podijeljen je u 4 faze, od kojih je svaka jednaka jednoj godini. Numerimo faze počevši od prve godine. Neka su X k i Y k sredstva dodijeljena preduzećima A i B u k-toj fazi. Tada je zbir X k + Y k =a k ukupan iznos sredstava utrošenih 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 se dobiti u k - toj fazi, kada se alociraju jedinice X k i Y k, biće 6X k + 1Y k . neka je maksimalni prihod dobijen u poslednjim fazama počevši od k - ta faza je f k (a k) jedinica. Napišimo funkcionalnu Bellmanovu jednačinu koja izražava princip optimalnosti: bez obzira na početno stanje i početno rešenje naknadno rješenje mora biti optimalno u odnosu na stanje koje proizlazi iz početnog stanja:

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

Funkcionalna Bellmanova jednačina će izgledati ovako:

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

(pošto je maksimum linearne funkcije postignut na kraju segmenta na x 4 = a 4);