Odredite grafičkom metodom minimum funkcije cilja. Pronađite ekstreme funkcije grafičkom metodom

ciljna funkcija- realna ili cjelobrojna funkcija više varijabli, podložna optimizaciji (minimizaciji ili maksimizaciji) u cilju rješavanja nekog optimizacijskog problema. Termin se koristi u matematičkom programiranju, istraživanju operacija, linearnom programiranju, teoriji statističke odluke i druge oblasti matematike, prvenstveno primijenjene prirode, iako cilj optimizacije može biti i rješenje samog matematičkog problema. Osim ciljna funkcija u problemu optimizacije, varijable se mogu ograničiti u obliku sistema jednakosti ili nejednakosti. AT opšti slučaj argumenti funkcije cilja mogu se specificirati na proizvoljnim skupovima.

Primjeri

Glatke funkcije i sistemi jednačina

Problem rješavanja bilo kojeg sistema jednačina

( F 1 (x 1 , x 2 , … , x M) = 0 F 2 (x 1 , x 2 , … , x M) = 0 … F N (x 1 , x 2 , … , x M) = 0 ( \displaystyle \left\((\begin(matrix)F_(1)(x_(1),x_(2),\ldots ,x_(M))=0\\F_(2)(x_(1),x_ (2),\ldots ,x_(M))=0\\\ldots \\F_(N)(x_(1),x_(2),\ldots ,x_(M))=0\end(matrica) )\u redu.)

može se formulisati kao problem minimiziranja funkcije cilja

S = ∑ j = 1 N F j 2 (x 1 , x 2 , … , x M) (1) (\displaystyle S=\sum _(j=1)^(N)F_(j)^(2)( x_(1),x_(2),\ldots ,x_(M))\qquad(1))

Ako su funkcije glatke, onda se problem minimizacije može riješiti metodom gradijenta.

Za bilo koju glatku funkciju cilja, može se izjednačiti sa 0 (\displaystyle 0) parcijalnim derivatima u odnosu na sve varijable. Optimalna funkcija cilja će biti jedno od rješenja takvog sistema jednačina. U slučaju funkcije (1) (\displaystyle (1)) ovo će biti sistem jednadžbi metode najmanjih kvadrata(MNK). Svako rješenje originalnog sistema je rješenje sistema najmanjih kvadrata. Ako je originalni sistem nekonzistentan, onda LSM sistem, koji uvijek ima rješenje, omogućava da se dobije približno rješenje originalnog sistema. Broj jednačina LSM sistema poklapa se sa brojem nepoznanica, što ponekad olakšava rješavanje zajedničkih početnih sistema.

Linearno programiranje

Ostalo poznati primjer ciljna funkcija je linearna funkcija koja se javlja u problemima linearnog programiranja. Za razliku od kvadratne funkcije cilja, optimizacija linearna funkcija moguće je samo ako postoje ograničenja u obliku sistema linearnih jednakosti ili nejednakosti.

Kombinatorna optimizacija

Tipičan primjer kombinatorne ciljne funkcije je ciljna funkcija problema trgovačkog putnika. Ova funkcija je jednaka dužini Hamiltonovog ciklusa na grafu. Ona je data na permutacijskom skupu n − 1 (\displaystyle n-1) vrhova grafa i određena je matricom dužine ruba grafa. Tačno rješenje takvih problema često se svodi na nabrajanje opcija.

Poglavlje 1. Izjava glavnog problema linearnog programiranja

1. Linearno programiranje

Linearno programiranje je grana matematičkog programiranja koja proučava metode za rješavanje ekstremnih problema koje karakteriziraju linearna zavisnost između varijabli i linearnog testa. Takvi problemi nalaze široku primjenu u raznim poljima ljudska aktivnost. Sistematsko proučavanje problema ovog tipa počelo je 1939–1940. u radovima L.V. Kantorovich.

Matematički problemi linearnog programiranja obuhvataju proučavanje specifičnih proizvodnih i ekonomskih situacija, koje se u jednom ili drugom obliku tumače kao problemi optimalnog korišćenja ograničenih resursa.

Spektar problema koji se rješavaju primjenom metoda linearnog programiranja je prilično širok, a to su npr.

problem optimalnog korišćenja resursa u planiranju proizvodnje;

problem mješavina (planiranje sastava proizvoda);

problem pronalaženja optimalne kombinacije različitih vrsta proizvoda za skladištenje u skladištima (upravljanje zalihama ili);

poslovi transporta (analiza lokacije preduzeća, kretanje robe).

Linearno programiranje je najrazvijeniji i najšire korišteni dio matematičkog programiranja (osim toga, ovo uključuje: cjelobrojno, dinamičko, nelinearno, parametarsko programiranje). Ovo se objašnjava na sljedeći način:

matematički modeli veliki broj ekonomski problemi su linearni u odnosu na potrebne varijable;

ova vrsta problema je trenutno najviše proučavana. Dizajniran za njega posebne metode, uz pomoć kojih se ovi zadaci rješavaju, i odgovarajući kompjuterski programi;

mnogi problemi linearnog programiranja, koji se rješavaju, našli su široku primjenu;

neki problemi koji nisu linearni u originalnoj formulaciji, nakon serije dodatna ograničenja a pretpostavke mogu postati linearne ili se mogu svesti na takav oblik da se mogu riješiti metodama linearnog programiranja.

Ekonomski i matematički model svakog problema linearnog programiranja uključuje: ciljnu funkciju čija se optimalna vrijednost (maksimalna ili minimalna) mora pronaći; ograničenja u formi sistema linearne jednačine ili nejednakosti; zahtjev nenegativnosti varijabli.

AT opšti pogled model je napisan na sljedeći način:

ciljna funkcija

(1.1) pod ograničenjima

(1.2) zahtjevi nenegativnosti

(1.3) gdje x j– varijable (nepoznate);

- koeficijenti problema linearnog programiranja.

Problem je pronaći optimalnu vrijednost funkcije (1.1) podložna ograničenjima (1.2) i (1.3).

Sistem ograničenja (1.2) naziva se funkcionalna ograničenja problema, a ograničenja (1.3) se nazivaju direktnim ograničenjima.

Vektor koji zadovoljava ograničenja (1.2) i (1.3) naziva se izvodljivo rješenje (plan) problema linearnog programiranja. Plan za koji funkcija (1.1) dosegne svoju maksimalnu (minimalnu) vrijednost naziva se optimalnim.

1.2. Simpleksna metoda za rješavanje problema linearnog programiranja

Simpleks metodu je razvio i prvi put primijenio za rješavanje problema 1947. godine američki matematičar J. Dantzig.

Problemi dvodimenzionalnog linearnog programiranja rješavaju se grafički. Za slučaj N=3, možemo razmotriti trodimenzionalni prostor i ciljna funkcija će dostići svoju optimalnu vrijednost na jednom od vrhova poliedra.

Dopustivo rješenje (dopustivi plan) LP problema datog u standardnom obliku je uređeni skup brojeva (x1, x2, ..., xn) koji zadovoljavaju ograničenja; je poenta u n-dimenzionalni prostor.

Mnogo izvodljiva rješenja formira domenu dopuštenih rješenja (ODS) LP problema. ODR je konveksni poliedar (poligon).

Uopšteno govoreći, kada su N-nepoznate uključene u problem, možemo reći da je područje izvodljivih rješenja, dato sistemom graničnih uslova, predstavljeno kao konveksni poliedar u n-dimenzionalnom prostoru i optimalna vrijednost ciljne funkcije se postiže na jednom ili više vrhova.

Rješenje se naziva osnovnim ako su sve slobodne varijable jednake nuli.

Referentno rješenje je osnovno nenegativno rješenje. Rješenje podrške može biti nedegenerirano i degenerirano. Rešenje za podršku se naziva nedegenerisano ako je broj njegovih nenulti koordinata jednak rangu sistema, u suprotnom je degenerisano.

Izvedivo rješenje, u kojem ciljna funkcija dosegne svoju ekstremnu vrijednost, naziva se optimalnim i označava se .

Vrlo je teško riješiti ove probleme grafički kada je broj varijabli veći od 3. Postoji univerzalni način rješavanje problema linearnog programiranja, nazvana simpleks metoda.

Simpleks metoda je univerzalna metoda za rješavanje LP problema, što je iterativni proces koji počinje s jednim rješenjem i, u potrazi za najboljom opcijom, kreće se duž uglovnih tačaka područja izvodljivih rješenja sve dok ne dostigne optimalnu vrijednost .

Može se koristiti za rješavanje bilo kojeg problema linearnog programiranja.

Simpleks metoda se temelji na ideji sukcesivnog poboljšanja rezultirajućeg rješenja.

Geometrijsko značenje simpleks metode sastoji se u uzastopnom prijelazu iz jednog vrha poliedra ograničenja u susjedni, u kojem funkcija cilja uzima najbolju (ili barem ne najgoru) vrijednost dok se ne pronađe optimalno rešenje- vrh u kojem se postiže optimalna vrijednost funkcije cilja (ako zadatak ima konačni optimum).

Dakle, svođenje sistema ograničenja na kanonski oblik(sva funkcionalna ograničenja su u obliku jednakosti), pronađite bilo koje osnovno rješenje ovog sistema, vodeći računa samo da ga pronađete što jednostavnije. Ako se prvo pronađeno osnovno rješenje pokazalo izvodljivim, onda se provjerava optimalnost. Ako nije optimalno, onda se prelazi na drugo, nužno prihvatljivo, osnovno rješenje. Simpleks metoda garantuje da se ovim novim rješenjem ciljna funkcija, ako ne dostigne optimum, približava (ili se barem ne udaljava od njega). S novim dopuštenim osnovnim rješenjem isto se radi dok se ne nađe rješenje koje je optimalno.

Proces primjene simpleks metode uključuje implementaciju njena tri glavna elementa:

metoda za određivanje nekog početnog izvodljivog osnovnog rješenja problema;

pravilo prelaska na najbolje (tačnije, ne na najgore) rješenje;

kriterij za provjeru optimalnosti pronađenog rješenja.

Simpleks metoda uključuje niz koraka i može se formulirati kao jasan algoritam (jasna instrukcija o implementaciji uzastopne operacije). To vam omogućava da ga uspješno programirate i implementirate na računaru. Problemi sa malim brojem varijabli i ograničenja mogu se riješiti simpleks metodom ručno.

6.1 Uvod

Optimizacija. Dio 1

Metode optimizacije omogućuju vam da odaberete najbolju opciju dizajna od svih opcije. AT poslednjih godina date su ove metode velika pažnja, te se kao rezultat toga razvila cela linija visoko efikasni algoritmi za pronalaženje najbolja opcija dizajnira pomoću kompjutera. Ovo poglavlje opisuje osnove teorije optimizacije, razmatra principe koji su u osnovi konstrukcije algoritama za optimalna rješenja, opisuje najpoznatije algoritme i analizira njihove prednosti i nedostatke.

6.2 Osnove teorije optimizacije

Termin "optimizacija" u literaturi se odnosi na proces ili niz operacija koji vam omogućavaju da dobijete rafinirano rješenje. Iako je krajnji cilj optimizacije pronaći najbolje, ili "optimalno" rješenje, obično se morate zadovoljiti poboljšanjem poznata rješenja nego ih usavršavati. Stoga je vjerojatnije da će se optimizacija shvatiti kao težnja za savršenstvom, koje se, možda, neće postići.

Uzimajući u obzir neke proizvoljan sistem, opisan m jednačinama sa n nepoznatih, postoje tri glavna tipa problema. Ako je m=n, problem se naziva algebarskim. Takav problem obično ima jedno rješenje. Ako je m>n, onda je problem redefiniran i po pravilu nema rješenja. Konačno, za m

Prije nego što pređemo na raspravu o pitanjima optimizacije, uvodimo nekoliko definicija.

Projektni parametri

Ovaj termin se odnosi na nezavisne varijabilni parametri, koji u potpunosti i nedvosmisleno definiraju projektni problem koji se rješava. Projektni parametri su nepoznate veličine čije se vrijednosti izračunavaju tokom procesa optimizacije. Kao projektni parametri mogu poslužiti bilo koje osnovne ili izvedene veličine koje služe za kvantitativno opisivanje sistema. Dakle, to mogu biti nepoznate vrijednosti dužine, mase, vremena, temperature. Broj projektnih parametara karakterizira stepen složenosti ovog problema dizajna. Obično se broj projektnih parametara označava sa n, a sami projektni parametri sa x sa odgovarajućim indeksima. Dakle, n projektnih parametara ovog problema će biti označeno sa

X1, x2, x3,...,xn.

ciljna funkcija

Ovo je izraz čiju vrijednost inženjer nastoji maksimizirati ili minimizirati. Funkcija cilja vam omogućava da kvantitativno uporedite dva alternativna rješenja. Sa matematičke tačke gledišta, funkcija cilja opisuje neku (n + 1) - dimenzionalnu površinu. Njegova vrijednost je određena projektnim parametrima

M=M(x 1 , x 2 ,...,x n).

Primeri funkcije cilja, koji se često susreću u inženjerskoj praksi, su cena, težina, snaga, dimenzije, efikasnost. Ako postoji samo jedan parametar dizajna, onda se funkcija cilja može predstaviti krivuljom na ravni (slika 6.1). Ako postoje dva projektna parametra, tada će ciljna funkcija biti predstavljena površinom u prostoru od tri dimenzije (slika 6.2). Sa tri ili više parametara dizajna, površine određene ciljnom funkcijom nazivaju se hiperpovršine i ne mogu se prikazati.

zheniya konvencionalnim sredstvima. Topološka svojstva površine ciljne funkcije igraju važnu ulogu u procesu optimizacije, jer od njih zavisi izbor najefikasnijeg algoritma.

Funkcija cilja u nekim slučajevima može poprimiti najneočekivanije oblike. Na primjer, nije uvijek moguće to izraziti

Slika 1. Jednodimenzionalna ciljna funkcija.

Slika 6.2.Dvodimenzionalna ciljna funkcija.

zatvoreno matematički oblik, u drugim slučajevima može

biti djelomično glatka funkcija. Funkcija cilja ponekad može zahtijevati tablicu tehničkih podataka (na primjer, tablicu stanja pare) ili može biti potrebno provesti eksperiment. U nekim slučajevima, parametri dizajna imaju samo cjelobrojne vrijednosti. Primjer bi bio broj zuba u zupčaniku ili broj vijaka u prirubnici. Ponekad parametri dizajna imaju samo dvije vrijednosti - da ili ne. Kvalitativne parametre, kao što su zadovoljstvo kupaca, pouzdanost, estetika, teško je uzeti u obzir u procesu optimizacije, jer ih je gotovo nemoguće kvantificirati. Međutim, u kojem god obliku je ciljna funkcija predstavljena, ona mora biti jednovrijedna funkcija projektnih parametara.

U brojnim problemima optimizacije potrebno je uvođenje više od jedne funkcije cilja. Ponekad jedan od njih može biti nekompatibilan s drugim. Primjer je dizajn aviona, kada se zahtijeva da se u isto vrijeme obezbijedi maksimalna snaga, minimalna težina i minimalni trošak. U takvim slučajevima, dizajner mora uvesti sistem prioriteta i svakoj funkciji cilja dodijeliti neki bezdimenzionalni množitelj. Kao rezultat, pojavljuje se “kompromisna funkcija” koja omogućava korištenje jedne složene ciljne funkcije u procesu optimizacije.

Pronalaženje minimuma i maksimuma

Neki algoritmi optimizacije su prilagođeni za pronalaženje maksimuma, drugi za pronalaženje minimuma. Međutim, bez obzira na vrstu ekstremnog problema koji se rješava, može se koristiti isti algoritam, jer se problem minimizacije lako može pretvoriti u problem pronalaženja maksimuma obrnutim predznakom ciljne funkcije. Ova tehnika je ilustrovana na slici 6.3.

Dizajnerski prostor

Ovo je naziv područja definiranog sa svih n projektnih parametara. Dizajnerski prostor nije tako velik kao što se čini, jer je obično ograničen na nekoliko

uslovi povezani sa fizičko lice zadataka. Ograničenja mogu biti toliko jaka da zadatak neće imati nikakvih

Slika 6.3 Promena predznaka funkcije cilja u suprotan

Maksimalni zadatak postaje minimalni zadatak.

zadovoljavajuće rješenje. Ograničenja se dijele u dvije grupe: ograničenja - jednakosti i ograničenja - nejednakosti.

Ograničenja - jednakost

Ograničenja – jednakosti – je zavisnost između projektnih parametara koja se mora uzeti u obzir pri pronalaženju rješenja. Oni odražavaju zakone prirode, ekonomije, prava, preovlađujući ukus i dostupnost potrebnih materijala. Broj ograničenja - jednakosti može biti bilo koji. Izgledaju kao

C 1 (x 1 , x 2 ,...,x n)=0,

C 2 (x 1 , x 2 ,...,x n)=0,

..................

C j (x 1 , x 2 ,...,x n)=0.

Ako se bilo koji od ovih odnosa može riješiti u odnosu na jedan od parametara dizajna, to vam omogućava da isključite ovaj parametar iz procesa optimizacije. Time se smanjuje broj dimenzija projektnog prostora i pojednostavljuje rješenje problema.

Ograničenja - nejednakosti

Ovo je posebna vrsta ograničenja izražena nejednakostima. U opštem slučaju, može ih biti bilo koji broj, i svi imaju oblik

z 1 r 1 (x 1 , x 2 ,...,x n) Z 1

z 2 r 2 (x 1 , x 2 ,...,x n) Z 2

.......................

z k r k (x 1 , x 2 ,...,x n) Z k

Treba napomenuti da se vrlo često, zbog ograničenja, optimalna vrijednost funkcije cilja ne postiže tamo gdje njena površina ima nulti gradijent. Često je najbolje rješenje na jednoj od granica domena dizajna.

Lokalni optimum

Ovo je naziv tačke u prostoru projektovanja u kojoj ciljna funkcija ima najveću vrednost u poređenju sa njenim vrednostima u svim drugim tačkama u njenom neposrednom okruženju.

Slika 6.4.Proizvoljna ciljna funkcija može imati nekoliko

lokalni optima.

Na sl. Slika 6.4 prikazuje jednodimenzionalnu ciljnu funkciju koja ima dva lokalna optimizma. Često projektni prostor sadrži mnogo lokalnih optima i mora se paziti da se prvi ne zamijeni za optimalno rješenje problema.

Global Optimum

Globalni optimum je optimalno rješenje za cjelokupni prostor za dizajn. Bolje je od svih ostalih rješenja koja odgovaraju lokalnom optimu, a to je ono što dizajner traži. Slučaj nekoliko jednakih globalnih optimuma smještenih u različitim dijelovima dizajn prostora. Kako se postavlja problem optimizacije najbolje je ilustrovano primjerom.

Primjer 6.1

Neka je potrebno dizajnirati pravougaoni kontejner zapremine 1 m, namenjen za transport neupakovanih vlakana. Poželjno je da se proizvodnja takvih kontejnera potroši što je više moguće manje materijala(pod pretpostavkom konstantne debljine zida, to znači da bi površina trebala biti minimalna), jer će biti jeftinije. Da bi kontejner bio pogodan za nošenje viljuškarom, njegova širina mora biti najmanje 1,5 m.

Hajde da formulišemo ovaj problem u obliku pogodnom za primenu optimizacionog algoritma.

Projektni parametri: x 1 , x 2 , x 3 .

Ciljna funkcija (koju treba minimizirati) je površina bočne površine kontejnera:

A=2(x 1 x 2 +x 2 x 3 +x 1 x 3), m2.

Ograničenje - jednakost:

Volumen = x 1 x 2 x 3 = 1m3.

Ograničenje - nejednakost:

Problemi linearnog programiranja

Linearno programiranje (LP) je jedna od sekcija matematičkog programiranja - disciplina koja proučava ekstremne (optimizacijske) probleme i razvija metode za njihovo rješavanje.

Problem optimizacije- ovo je matematički problem, koji se sastoji u pronalaženju optimalne (tj. maksimalne ili minimalne) vrijednosti funkcije cilja, a vrijednosti varijabli moraju pripadati određenom području dozvoljene vrijednosti(ODZ).

Općenito, formulacija ekstremnog problema matematičkog programiranja sastoji se u određivanju najveće ili najmanje vrijednosti funkcije, tzv. ciljna funkcija, pod uslovima (ograničenjima), gdje i – unapred definisane funkcije, i dati su konstante. Istovremeno, ograničenja u obliku jednakosti i nejednakosti određuju skup (region) izvodljivih rješenja (ODS), a nazivaju se parametri dizajna.

U zavisnosti od vrste funkcija i problema matematičko programiranje se dijele na više klasa (linearno, nelinearno, konveksno, cjelobrojno, stohastičko, dinamičko programiranje itd.).

AT opšti pogled LP problem ima sljedeći pogled:

, (5.1)

, , (5.2)

, , (5.3)

gdje su , , date konstante.

Funkcija (5.1) naziva se funkcija cilja; sistemi (5.2), (5.3) - sistemom ograničenja; uvjet (5.4) je uvjet nenegativnosti projektnih parametara.

Skup projektnih parametara koji zadovoljavaju ograničenja (5.2), (5.3) i (5.4) naziva se prihvatljivo rešenje ili plan.

Optimalno rješenje ili optimalan plan LP problem se naziva izvodljivim rješenjem, u kojem ciljna funkcija (5.1) uzima optimalnu (maksimalnu ili minimalnu) vrijednost.

Standardni zadatak LP se naziva problem pronalaženja maksimalne (minimalne) vrijednosti ciljne funkcije (5.1) pod uslovom (5.2) i (5.4), gdje je , , tj. one. ograničenja samo u obliku nejednakosti (5.2) i svi projektni parametri zadovoljavaju uslov nenegativnosti, a ne postoje uvjeti u obliku jednakosti:

,

, , (5.5)

.

Kanonski (glavni) zadatak LP se naziva problem pronalaženja maksimalne (minimalne) vrijednosti ciljne funkcije (5.1) pod uslovom (5.3) i (5.4), gdje je , , tj. one. ograničenja samo u obliku jednakosti (5.3) i svi projektni parametri zadovoljavaju uvjet nenegativnosti, a ne postoje uvjeti u obliku nejednakosti:

,

.

Kanonski LP problem se također može napisati u matričnom i vektorskom obliku.

Matrični oblik kanonskog LP problema ima sljedeći oblik:

Vektorski oblik kanonskog LP problema.

KONTROLNI RAD NA DISCIPLINI:

"METODE OPTIMALNIH REŠENJA"

Opcija broj 8

1. Riješite problem linearnog programiranja pomoću grafičke metode. Pronađite maksimum i minimum funkcije  pod datim ograničenjima:

,

.

Rješenje

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

9x1 +3x2 ≥30, (1)

X 1 + x 2 ≤4, (2)

x 1 + x 2 ≤8, (3)

Konstruirajmo domenu dopuštenih rješenja, tj. grafički riješiti sistem nejednačina. Da bismo to uradili, konstruišemo svaku pravu liniju i definišemo poluravnine date nejednačinama (poluravnine su označene prostim brojem).

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

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

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

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

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

Razmotrite ciljnu funkciju problema.

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

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

.

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

odgovor:
i
.

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

.

Rješenje

Rešimo direktni problem linearnog programiranja simpleks metodom, koristeći simpleks tablicu.

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

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

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

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

Da bismo postavili zadatak za minimum, pišemo funkciju cilja na sljedeći način: .

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

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

Štoviše, umjetne varijable nisu povezane sa sadržajem zadatka, ali vam omogućavaju da izgradite početnu točku, a proces optimizacije prisiljava te varijable da uzmu nulte vrijednosti i osiguraju prihvatljivost optimalnog rješenja.

Iz jednadžbi izražavamo umjetne varijable: x 6 \u003d 4-x 1 -x 2 +x 3, koje zamjenjujemo u ciljnu funkciju: ili.

Matrica koeficijenata
ovaj sistem jednačina ima oblik:
.

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

Pod pretpostavkom da su slobodne varijable 0, dobijamo prvu osnovnu liniju:

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

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

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

Trenutna osnovna linija nije optimalna jer postoje pozitivni koeficijenti u retku indeksa. Odabraćemo kolonu koja odgovara varijabli x 2 kao vodeći, jer je to najveći koeficijent. Izračunajte vrijednosti D i i odaberite najmanji od njih: min(4:1, 2:2, 10:2) = 1.

Dakle, 2. red je vodeći.

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

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

Formiramo sljedeći dio tabele simpleksa. Umjesto varijable x 4, varijabla x 2 će ući u plan 1.

Linija koja odgovara varijabli x 2 u planu 1 dobija se dijeljenjem svih elemenata linije x 4 plana 0 sa elementom omogućavanja RE=2. Umjesto elementa za rješavanje, dobijamo 1. U preostale ćelije kolone x 2 upisujemo nule.

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

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

Trenutna osnovna linija nije optimalna jer postoje pozitivni koeficijenti u retku indeksa. Odabraćemo kolonu koja odgovara varijabli x 1 kao vodeći, jer je to najveći koeficijent. Izračunajte vrijednosti D i po redovima kao količnik dijeljenja: a od njih biramo najmanji: min (3: 1 1 / 2, -, 8: 2) = 2.

Dakle, 1. red je vodeći.

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

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

Formiramo sljedeći dio tabele simpleksa. Umjesto varijable x 6, varijabla x 1 će biti uključena u plan 2.

Dobijamo novu simpleks tabelu:

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

Nijedna vrijednost reda indeksa nije pozitivna. Stoga ova tabela određuje optimalni plan zadatka.

Konačna verzija simpleks tabele:

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

Pošto u optimalnom rješenju nema umjetnih varijabli (jednake su nuli), onda ovu odluku važi.

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

Odgovori:
,
.

3. Firma "Tri debela" bavi se isporukom mesnih konzervi iz tri skladišta koja se nalaze u različitim delovima grada do tri prodavnice. Dostupne zalihe konzervirane hrane u skladištima, kao i količine narudžbi iz trgovina i cijene dostave (uslovno novčane jedinice) prikazani su u transportnoj tabeli.

Pronađite plan transporta koji pruža najmanje gotovinske troškove (izvedite originalni plan transporta koristeći metodu "sjeverozapadnog ugla").

Rješenje

Provjerimo neophodan i dovoljan uslov za rješivost problema:

= 300 + 300 + 200 = 800 .

= 250 + 400 + 150 = 800.

Uslov ravnoteže je ispunjen. Zalihe jednake potrebama. Stoga je model transportnog problema zatvoren.

Unesimo početne podatke u tabelu distribucije.

Potrebe

Koristeći metodu sjeverozapadnog ugla, izgradićemo prvi osnovni plan transportnog problema.

Plan počinje da se popunjava iz gornjeg lijevog ugla.

Željeni element je 4. Za ovaj element zalihe su 300, potrebe su 250. Pošto je minimum 250, oduzimamo ga: .

			300 - 250 = 50
250 - 250 = 0

Željeni element je 2. Za ovaj element zalihe su 50, potrebe su 400. Pošto je minimum 50, oduzimamo ga: .

			50 - 50 = 0
	400 - 50 = 350

Željeni element je 5. Za ovaj element zalihe su 300, potrebe su 350. Pošto je minimum 300, oduzimamo ga:

			300 - 300 = 0
	350 - 300 = 50

Željeni element je 3. Za ovaj element zalihe su 200, potrebe su 50. Pošto je minimum 50, oduzimamo ga:

			200 - 50 = 150
	50 - 50 = 0

Željeni element je 6. Za ovaj element zalihe su 150, potrebe su 150. Pošto je minimum 150, oduzimamo ga:

			150 - 150 = 0
		150 - 150 = 0

Potrebe

Konstruirajmo na ravni skup dopuštenih rješenja sistema linearne nejednakosti i geometrijski pronaći minimalnu vrijednost ciljne funkcije.

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. Sastaviti matematički model problema i riješiti ga korištenjem simpleks metode.
• 2. Sastaviti matematički model dualnog problema, zapisati 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 su sve delte veće od nule, onda je dalje povećanje vrijednosti funkcije cilja f nemoguće i dobili smo optimalan plan.

Ako u problemu linearnog programiranja postoje samo dvije varijable, on se 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 sistemu ograničenja mogu biti prisutni i znakovi i znaci.

Izgradnja domena izvodljivih rješenja

Grafička metoda rješavanja problema (1) je sljedeća.
Prvo crtamo koordinatne osi i odabiremo razmjer. Svaka od nejednačina sistema ograničenja (1.2) definira poluravninu ograničenu odgovarajućom pravom.

Dakle, prva nejednakost
(1.2.1)
definira poluravninu ograničenu pravom. S jedne strane ove linije, a s druge strane. Na pravoj liniji. Da bismo saznali sa koje strane je nejednakost (1.2.1) zadovoljena, biramo proizvoljna tačka ne leži na pravoj liniji. Zatim zamjenjujemo koordinate ove tačke u (1.2.1). Ako nejednakost vrijedi, tada poluravnina sadrži odabranu tačku. Ako nejednakost nije zadovoljena, tada se poluravnina nalazi na drugoj strani (ne sadrži odabranu tačku). Osjenčamo poluravninu za koju je zadovoljena nejednakost (1.2.1).

Isto radimo i za preostale nejednakosti sistema (1.2). Tako dobijamo zasjenjene poluravnine. Tačke domena dopuštenih rješenja zadovoljavaju sve nejednakosti (1.2). Dakle, grafički, područje izvodljivih rješenja (ODD) je sjecište svih konstruiranih poluravnina. Zasjenimo ODR. To je konveksan poligon čija lica pripadaju konstruisanim linijama. Također, ODR može biti neograničena konveksna figura, segment, zraka ili prava linija.

Može se pojaviti i slučaj da poluravnine ne sadrže zajedničke tačke. Tada je domen dopustivih rješenja prazan skup. Ovaj problem nema rješenja.

Možete pojednostaviti metodu. Ne možete zasjeniti svaku poluravninu, već prvo izgradite sve linije
(2)
Zatim odaberite proizvoljnu tačku koja ne pripada nijednoj od ovih linija. Zamenimo koordinate ove tačke u sistem nejednačina (1.2). Ako su sve nejednakosti zadovoljene, tada je područje izvodljivih rješenja ograničeno konstruiranim linijama i uključuje odabranu tač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 tačku. I tako dalje, sve dok se ne pronađe jedna tačka čije koordinate zadovoljavaju sistem (1.2).

Pronalaženje ekstrema ciljne funkcije

Dakle, imamo zasjenjeno područje izvodljivih rješenja (ODD). Omeđena je isprekidanom linijom koja se sastoji od segmenata i zraka koji pripadaju konstruisanim linijama (2). ODR je uvijek konveksan skup. Može biti kao ograničen set, i nije ograničeno na nekim pravcima.

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

Da biste to učinili, odaberite bilo koji broj i napravite pravu liniju
(3) .
Radi pogodnosti daljeg predstavljanja, pretpostavljamo da ova prava linija prolazi kroz ODS. Na ovoj pravoj liniji, ciljna funkcija je konstantna i jednaka . takva prava linija naziva se linija nivoa funkcije. Ova linija dijeli ravan na dvije poluravnine. U jednoj poluravni
.
Na drugoj polovini ravni
.
Odnosno, na jednoj strani prave (3) ciljna funkcija raste. I što više odmaknemo tačku od prave (3), to će vrijednost biti veća. S druge strane prave linije (3) ciljna funkcija opada. I što više odmaknemo tačku od prave (3) na drugu stranu, vrijednost će biti manja. Ako povučemo liniju paralelnu s linijom (3), tada će nova linija također biti linija nivoa ciljne funkcije, ali s drugom vrijednošću.

Dakle, da bi se pronašla maksimalna vrijednost ciljne funkcije, potrebno je povući pravu liniju paralelnu pravoj liniji (3), što je dalje moguće od nje u smjeru povećanja vrijednosti , i koja prolazi kroz najmanje jednu tačku ODT-a. Da biste pronašli minimalnu vrijednost ciljne funkcije, potrebno je povući pravu liniju paralelnu pravoj liniji (3) i što je dalje moguće od nje u smjeru opadanja vrijednosti , i koja prolazi kroz barem jednu tačku ODT-a.

Ako je ODE neograničen, onda može nastati slučaj kada se takva prava linija ne može povući. Odnosno, bez obzira na to kako uklonimo pravu liniju sa linije (3) u smjeru povećanja (opadanja), prava će uvijek prolaziti kroz ODR. U ovom slučaju može biti proizvoljno veliko (malo). Dakle, ne postoji maksimalna (minimalna) vrijednost. Problem nema rješenja.

Razmotrimo slučaj kada ekstremna prava paralelna sa proizvoljnom linijom oblika (3) prolazi kroz jedan vrh ODD poligona. Iz grafa određujemo koordinate ovog vrha. Tada se maksimalna (minimalna) vrijednost ciljne funkcije određuje formulom:
.
Rješenje problema je
.

Takođe može postojati slučaj kada je prava linija paralelna sa jednom od lica ODS-a. Tada linija prolazi kroz dva vrha ODD poligona. Određujemo koordinate ovih vrhova. Da biste odredili maksimalnu (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

Kompanija proizvodi haljine dva modela A i B. Koriste se tri vrste tkanina. Za izradu jedne haljine modela A 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 prvog tipa su 21 m, drugog tipa - 10 m, trećeg tipa - 16 m. Izdavanje jednog proizvoda tipa A donosi prihod od 400 den. jedinica, jedan proizvod tipa B - 300 den. jedinice

Napravite proizvodni plan koji kompaniji daje najveći prihod. Riješite problem grafički.

Rješenje

Označimo varijable i broj proizvedenih haljina modela A i B, respektivno. Tada će količina upotrebljenog 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ći tip će biti:
(m)
Pošto broj proizvedenih haljina ne može biti negativan
i .
Prihod od proizvedenih haljina će biti:
(den. jedinice)

Tada ekonomsko-matematički model problema ima oblik:

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

Gradimo pravu liniju.
U .
U .
Kroz tačke (0; 7) i (10.5; 0) povlačimo pravu liniju.

Gradimo pravu liniju.
U .
U .
Kroz tačke (0; 10) i (10; 0) povlačimo pravu liniju.

Gradimo pravu liniju.
U .
U .
Kroz tačke (0; 8) i (8; 0) povlačimo pravu liniju.

Osjenčamo područje tako da tačka (2; 2) padne u zasjenjeni dio. Dobijamo četvorougao OABC.

(P1.1) .
U .
U .
Kroz tačke (0; 4) i (3; 0) povlačimo pravu liniju.

Nadalje, primjećujemo da budući da su koeficijenti za i ciljne funkcije pozitivni (400 i 300), onda se povećava s povećanjem i . Povlačimo pravu liniju paralelnu pravoj liniji (A1.1), što je dalje moguće od nje u smjeru porasta i koja prolazi barem kroz jednu tačku četverougla OABC. Takva prava linija prolazi kroz tačku C. Iz konstrukcije određujemo njene koordinate.
.

Rješenje problema: ;

Odgovori

.
Odnosno, da bi se ostvario 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 pomoću grafičke metode.

Rješenje

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

Gradimo pravu liniju.
U .
U .
Kroz tačke (0; 6) i (6; 0) povlačimo pravu liniju.

Gradimo pravu liniju.
Odavde.
U .
U .
Kroz tačke (3; 0) i (7; 2) povlačimo pravu liniju.

Gradimo pravu liniju.
Gradimo pravu liniju (os apscisa).

Područje dopuštenih rješenja (DDR) ograničeno je konstruiranim pravim linijama. Da bismo saznali s koje strane, primjećujemo da tačka pripada ODT-u, budući da zadovoljava sistem nejednačina:

Osjenčamo područje duž granica konstruisanih linija tako da tačka (4; 1) padne u zasjenjeni dio. Dobijamo trougao ABC.

Konstruiramo liniju proizvoljnog nivoa ciljne funkcije, na primjer,
.
U .
U .
Kroz tačke (0; 6) i (4; 0) povlačimo ravnu liniju.
Budući da se ciljna funkcija povećava s povećanjem i , nacrtamo pravu liniju, paralelna linija nivou i što je dalje moguće od njega u pravcu povećanja , i prolazeći kroz najmanje jednu tačku trougla ABC. Takva prava linija prolazi kroz tačku C. Iz konstrukcije određujemo njene koordinate.
.

Rješenje problema: ;

Odgovori

Primjer bez rješenja

Zadatak

Riješite grafički problem linearnog programiranja. Pronađite maksimalnu i minimalnu vrijednost funkcije cilja.

Rješenje

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

Gradimo pravu liniju.
U .
U .
Kroz tačke (0; 8) i (2.667; 0) povlačimo pravu liniju.

Gradimo pravu liniju.
U .
U .
Kroz tačke (0; 3) i (6; 0) povlačimo pravu liniju.

Gradimo pravu liniju.
U .
U .
Kroz tačke (3; 0) i (6; 3) povlačimo pravu liniju.

Prave i su koordinatne ose.

Područje dopuštenih rješenja (SDR) ograničeno je konstruiranim pravim linijama i koordinatnim osa. Da bismo saznali s koje strane, primjećujemo da tačka pripada ODT-u, budući da zadovoljava sistem nejednačina:

Osjenčamo područje tako da tačka (3; 3) padne u zasjenjeni dio. Dobijamo neograničeno područje ograničeno izlomljenom linijom ABCDE.

Konstruiramo liniju proizvoljnog nivoa ciljne funkcije, na primjer,
(P3.1) .
U .
U .
Kroz tačke (0; 7) i (7; 0) povlačimo pravu liniju.
Budući da su koeficijenti na i pozitivni, onda raste s povećanjem i .

Da biste pronašli maksimum, potrebno je povući paralelnu liniju, što je dalje moguće u smjeru povećanja, i koja prolazi kroz barem jednu tačku regije ABCDE. Međutim, pošto je područje neograničeno sa strane velike vrijednosti i , tada se takva prava linija ne može povući. Koju god pravu liniju nacrtamo, uvijek će postojati tačke u regiji koje su udaljenije u smjeru povećanja i . Dakle, ne postoji maksimum. možete ga učiniti velikim koliko želite.

Tražimo minimum. Povlačimo pravu liniju paralelnu pravoj liniji (A3.1) i što je dalje moguće od nje u smjeru opadanja , i koja prolazi kroz barem jednu tačku područja ABCDE. Takva prava linija prolazi kroz tačku C. Iz konstrukcije određujemo njene koordinate.
.
Minimalna vrijednost ciljna funkcija:

Odgovori

Ne postoji maksimalna vrijednost.
Minimalna vrijednost
.