Tretí riadok vydelíme kľúčovým prvkom rovným 5, dostaneme tretí riadok novej tabuľky.

Základné stĺpce zodpovedajú jednotlivým stĺpcom.

Výpočet zostávajúcich tabuľkových hodnôt:

"BP - základný plán":

; ;

"x1": ; ;

"x5": ; .

Hodnoty riadku indexu sú nezáporné, preto získame optimálne riešenie: , ; .

odpoveď: maximálny zisk z predaja vyrobených výrobkov vo výške 160/3 jednotiek je zabezpečený uvoľnením iba výrobkov druhého typu v množstve 80/9 jednotiek.

Úloha číslo 2

Problém nelineárneho programovania je daný. Nájdite maximum a minimum účelovej funkcie pomocou grafovo-analytickej metódy. Zostavte Lagrangeovu funkciu a ukážte, že v extrémnych bodoch sú splnené dostatočné minimálne (maximálne) podmienky.

Pretože posledná číslica šifry je 8, potom A=2; B = 5.

Pretože predposledná číslica šifry je 1, potom by ste mali zvoliť úlohu číslo 1.

Riešenie:

1) Nakreslíme oblasť, ktorú vymedzuje systém nerovností.

Táto oblasť je trojuholník ABC so súradnicami vrcholov: A(0; 2); B(4; 6) a C(16/3; 14/3).

Úrovne cieľových funkcií sú kruhy so stredom v bode (2; 5). Druhé mocniny polomerov budú hodnotami cieľovej funkcie. Potom obrázok ukazuje, že minimálna hodnota účelovej funkcie sa dosiahne v bode H, maximálna hodnota je buď v bode A alebo v bode C.

Hodnota účelovej funkcie v bode A: ;

Hodnota účelovej funkcie v bode C: ;

To znamená, že maximálna hodnota funkcie je dosiahnutá v bode A(0; 2) a rovná sa 13.

Nájdite súradnice bodu H.

Ak to chcete urobiť, zvážte systém:

ó

ó

Čiara je dotyčnicou kružnice, ak má rovnica jedinečné riešenie. Kvadratická rovnica má jedinečné riešenie, ak je diskriminant 0.

Potom ; ; - minimálna hodnota funkcie.

2) Vytvorte Lagrangeovu funkciu, aby ste našli minimálne riešenie:

O X 1 =2.5; X 2 =4.5 dostaneme:

ó

Systém má riešenie pre , t.j. sú splnené dostatočné extrémne podmienky.

Na nájdenie maximálneho riešenia zostavíme Lagrangeovu funkciu:

Dostatočné podmienky pre extrém:

O X 1 =0; X 2 =2 dostaneme:

ó ó

Systém má aj riešenie, t.j. sú splnené dostatočné extrémne podmienky.

odpoveď: minimum cieľovej funkcie sa dosiahne pri ; ; maximálna účelová funkcia sa dosiahne vtedy ; .

Úloha číslo 3

Dvom podnikom sú pridelené finančné prostriedky vo výške d Jednotky. Pri pridelení prvému podniku na rok X jednotiek fondov, z ktorých poskytuje príjem k 1 X jednotky a pri pridelení druhému podniku r jednotiek fondov, poskytuje príjem k 1 r Jednotky. Stav prostriedkov na konci roka za prvý podnik sa rovná nx a za druhé môj. Ako rozložiť všetky prostriedky do 4 rokov tak, aby celkový príjem bol čo najväčší? Vyriešte problém dynamickým programovaním.

i = 8, k = 1.

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

Riešenie:

Celé obdobie 4 rokov je rozdelené do 4 etáp, z ktorých každá sa rovná jednému roku. Očíslujme etapy od prvého ročníka. Nech X k a Y k sú finančné prostriedky pridelené podnikom A a B v k-tej fáze. Potom súčet X k + Y k =a k je celkový objem prostriedkov použitých v k - tej etape a zostávajúcich z predchádzajúcej etapy k - 1. v prvej etape sú použité všetky pridelené prostriedky a 1 = 2200 jednotiek. príjem, ktorý sa získa vo fáze k, keď sa pridelia jednotky X k a Y k, bude 6X k + 1Y k . nech maximálny príjem získaný v posledných fázach počnúc od k - tejto fáze je f k (ak) jednotiek. Napíšme Bellmanovu funkčnú rovnicu vyjadrujúcu princíp optimality: bez ohľadu na počiatočný stav a počiatočné riešenie, následné riešenie musí byť optimálne vzhľadom na stav získaný ako výsledok počiatočného stavu:

Pre každú fázu musíte vybrať hodnotu X k a hodnotu Y k=ak- Xk. S ohľadom na to nájdeme príjem v k-tej fáze:

Funkčná Bellmanova rovnica bude vyzerať takto:

Zvážte všetky fázy, počnúc poslednou.

(keďže maximum lineárnej funkcie sa dosiahne na konci segmentu pri x 4 = a 4);

KONTROLNÁ PRÁCA NA DISCIPLÍNE:

"METÓDY OPTIMÁLNYCH RIEŠENÍ"

Možnosť číslo 8

1. Vyriešte problém lineárneho programovania pomocou grafickej metódy. Nájdite maximum a minimum funkcie  pod danými obmedzeniami:

,

.

Riešenie

Je potrebné nájsť minimálnu hodnotu účelovej funkcie a maximum v rámci systému obmedzení:

9x1 +3x2 ≥30, (1)

X 1 + x 2 ≤ 4, (2)

x 1 + x 2 ≤ 8, (3)

Zostrojme doménu prípustných riešení, t.j. vyriešiť graficky systém nerovností. Na to zostrojíme každú priamku a definujeme polroviny dané nerovnicami (polroviny sú označené prvočíslom).

Priesečníkom polrovín bude oblasť, ktorej súradnice bodov spĺňajú podmienku nerovností sústavy obmedzení úlohy. Označme hranice oblasti polygónu riešenia.

Zostrojme priamku zodpovedajúcu hodnote funkcie F = 0: F = 2x 1 +3x 2 = 0. Gradientový vektor zložený z koeficientov účelovej funkcie udáva smer minimalizácie F(X). Začiatok vektora je bod (0; 0), koniec je bod (2; 3). Posuňme túto čiaru paralelným spôsobom. Keďže nás zaujíma minimálne riešenie, posúvame priamku až po prvý dotyk určenej oblasti. Na grafe je táto čiara označená bodkovanou čiarou.

Rovno
pretína oblasť v bode C. Keďže bod C je získaný ako výsledok priesečníka priamok (4) a (1), jeho súradnice spĺňajú rovnice týchto priamok:
.

Po vyriešení sústavy rovníc dostaneme: x 1 = 3,3333, x 2 = 0.

Kde nájdeme minimálnu hodnotu účelovej funkcie: .

Zvážte objektívnu funkciu problému.

Zostrojme priamku zodpovedajúcu hodnote funkcie F = 0: F = 2x 1 +3x 2 = 0. Gradientový vektor zložený z koeficientov účelovej funkcie udáva smer maximalizácie F(X). Začiatok vektora je bod (0; 0), koniec je bod (2; 3). Posuňme túto čiaru paralelným spôsobom. Keďže nás zaujíma maximálne riešenie, posúvame priamku až po posledný dotyk určenej plochy. Na grafe je táto čiara označená bodkovanou čiarou.

Rovno
pretína oblasť v bode B. Keďže bod B je získaný ako výsledok priesečníka priamok (2) a (3), jeho súradnice spĺňajú rovnice týchto priamok:

.

Kde nájdeme maximálnu hodnotu účelovej funkcie: .

odpoveď:
a
.

2 . Vyriešte problém lineárneho programovania pomocou simplexnej metódy:

.

Riešenie

Vyriešme priamy problém lineárneho programovania simplexovou metódou pomocou simplexnej tabuľky.

Určme minimálnu hodnotu účelovej funkcie
za nasledujúcich podmienok - obmedzení:
.

Na zostavenie prvého referenčného plánu redukujeme systém nerovností na systém rovníc zavedením ďalších premenných.

V 1. významovej nerovnosti (≥) uvádzame základnú premennú X 3 so znamienkom mínus. V 2. významovej nerovnosti (≤) uvádzame základnú premennú X 4 . V 3. význame nerovnosť (≤) zavádzame základnú premennú x 5 .

Zavedieme umelé premenné : v 1. rovnosti zavádzame premennú X 6 ;

Na nastavenie úlohy na minimum napíšeme účelovú funkciu takto: .

Za použitie umelých premenných zavedených do účelovej funkcie sa ukladá takzvaná penalizácia M, veľmi veľké kladné číslo, ktoré zvyčajne nie je špecifikované.

Výsledný základ sa nazýva umelý a metóda riešenia sa nazýva metóda umelého základu.

Okrem toho umelé premenné nesúvisia s obsahom úlohy, ale umožňujú vám vytvoriť východiskový bod a proces optimalizácie núti tieto premenné nadobúdať nulové hodnoty a zabezpečiť prípustnosť optimálneho riešenia.

Z rovníc vyjadríme umelé premenné: x 6 \u003d 4-x 1 -x 2 +x 3, ktoré dosadíme do účelovej funkcie: alebo.

Koeficientová matica
tento systém rovníc má tvar:
.

Poďme riešiť sústavu rovníc vzhľadom na základné premenné: X 6 , X 4 , X 5.

Za predpokladu, že voľné premenné sú 0, dostaneme prvú základnú čiaru:

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

Základné riešenie sa nazýva prípustné, ak nie je záporné.

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

Aktuálna základná línia nie je optimálna, pretože v riadku indexu sú kladné koeficienty. Stĺpec zodpovedajúci premennej x 2 zvolíme ako vedúci, keďže ide o najväčší koeficient. Vypočítajte hodnoty D i a vyberte najmenšiu z nich: min(4: 1, 2: 2, 10: 2) = 1.

Preto vedie 2. riadok.

Rozlišovací prvok sa rovná (2) a nachádza sa v priesečníku vodiaceho stĺpca a vodiaceho radu.

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

Tvoríme ďalšiu časť simplexnej tabuľky. Namiesto premennej x 4 vstúpi do plánu 1 premenná x 2.

Čiara zodpovedajúca premennej x 2 v pláne 1 sa získa vydelením všetkých prvkov čiary x 4 plánu 0 povoľovacím prvkom RE=2. Namiesto rozlišovacieho prvku dostaneme 1. Do zvyšných buniek stĺpca x 2 napíšeme nuly.

V novom pláne je teda vyplnený 1 riadok x 2 a stĺpec x 2. Všetky ostatné prvky nového plánu 1, vrátane prvkov indexového riadku, sú určené pravidlom obdĺžnika.

		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

Aktuálna základná línia nie je optimálna, pretože v riadku indexu sú kladné koeficienty. Stĺpec zodpovedajúci premennej x 1 zvolíme ako vedúci, keďže ide o najväčší koeficient. Vypočítajte hodnoty D i po riadkoch ako podiel delenia: a z nich vyberieme najmenšie: min (3: 1 1 / 2, -, 8: 2) = 2.

Preto vedie 1. línia.

Rozlišovací prvok sa rovná (1 1 / 2) a nachádza sa na priesečníku vedúceho stĺpca a vedúceho radu.

		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

Tvoríme ďalšiu časť simplexnej tabuľky. Namiesto premennej x 6 bude do plánu 2 zahrnutá premenná x 1.

Získame novú simplexnú tabuľku:

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

Žiadna z hodnôt riadka indexu nie je kladná. Preto táto tabuľka určuje optimálny plán úloh.

Konečná verzia simplexnej tabuľky:

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

Keďže v optimálnom riešení nie sú žiadne umelé premenné (rovnajú sa nule), je toto riešenie realizovateľné.

Optimálny plán možno napísať takto: x 1 \u003d 2, x 2 \u003d 2:.

Odpoveď:
,
.

3. Spoločnosť „Traja tuční muži“ sa zaoberá dodávkou mäsových konzerv z troch skladov nachádzajúcich sa v rôznych častiach mesta do troch predajní. Zásoby konzervovaných potravín dostupné v skladoch, ako aj objem objednávok z obchodov a sadzby za doručenie (v konvenčných peňažných jednotkách) sú uvedené v tabuľke dopravy.

Nájdite plán dopravy, ktorý poskytuje najnižšie peňažné náklady (vykonajte pôvodný plán dopravy pomocou metódy „severozápadného rohu“).

Riešenie

Skontrolujme nevyhnutnú a postačujúcu podmienku pre riešiteľnosť problému:

= 300 + 300 + 200 = 800 .

= 250 + 400 + 150 = 800.

Podmienka rovnováhy je splnená. Zásoby rovnaké potreby. Preto je model dopravného problému uzavretý.

Do distribučnej tabuľky zadáme počiatočné údaje.

Potreby

Metódou severozápadného rohu zostrojíme prvý základný plán dopravnej úlohy.

Plán sa začína vypĺňať z ľavého horného rohu.

Požadovaný prvok je 4. Pre tento prvok sú zásoby 300, potreby 250. Keďže minimum je 250, odčítame: .

			300 - 250 = 50
250 - 250 = 0

Požadovaný prvok je 2. Pre tento prvok sú zásoby 50, potreby 400. Keďže minimum je 50, odpočítame: .

			50 - 50 = 0
	400 - 50 = 350

Požadovaný prvok je 5. Pre tento prvok sú zásoby 300, potreby sú 350. Keďže minimum je 300, odpočítame ho:

			300 - 300 = 0
	350 - 300 = 50

Požadovaný prvok je 3. Pre tento prvok sú zásoby 200, potreby sú 50. Keďže minimum je 50, odpočítame ho:

			200 - 50 = 150
	50 - 50 = 0

Požadovaný prvok je 6. Pre tento prvok sú zásoby 150, potreby sú 150. Keďže minimum je 150, odpočítame ho:

			150 - 150 = 0
		150 - 150 = 0

Potreby

Nájdite pomocou grafickej metódy maximum účelovej funkcie

F= 2X 1 + 3X 2 ® max

S obmedzeniami

Riešenie pomocou excelovských tabuliek

Najprv si postavme riešenie sústavy nerovností na excelovskom hárku.

Zvážte prvú nerovnosť.

Zostrojme hraničnú čiaru z dvoch bodov. Označte riadok (L1) (alebo Row1). Súradnice X 2 počítame podľa vzorcov:

Ak chcete zostaviť, vyberte bodový graf

Výber údajov pre priamku

Zmeňte názov riadku:

Vyberte rozloženie grafu. Zmeňte názov súradnicových osí:

Priama čiara (L1) na grafe:

Riešenie striktnej nerovnosti možno nájsť pomocou jedného testovacieho bodu, ktorý nepatrí do priamky (L1). Napríklad pomocou bodu (0; 0)W(L1).

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

Nerovnosť je pravdivá, preto riešením nerovnosti (1) bude polrovina, v ktorej sa nachádza testovací bod (na obrázku pod čiarou L1).

Potom riešime nerovnosť (2) .

Zostrojme hraničnú čiaru 2 z dvoch bodov. Označte čiaru (L2).

Priama čiara (L2) na grafe:

Riešenie striktnej nerovnosti 2 možno nájsť pomocou jediného testovacieho bodu, ktorý nepatrí do priamky (L2). Napríklad pomocou bodu (0; 0)W(L2).

Dosadením súradníc bodu (0; 0) dostaneme nerovnosť

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

Nerovnosť je pravdivá, preto riešením nerovnosti (2) bude polrovina, v ktorej sa nachádza testovací bod (na obrázku nižšie čiara L2).

Potom riešime nerovnosť (3) .

Zostrojme hraničnú čiaru z dvoch bodov. Označte čiaru (L3).

Priama čiara (L3) na grafe:

Riešenie striktnej nerovnosti 2 možno nájsť pomocou jediného testovacieho bodu, ktorý nepatrí do priamky (L3). Napríklad pomocou bodu (0; 0)W(L3).

Dosadením súradníc bodu (0; 0) dostaneme nerovnosť

Nerovnosť je pravdivá, preto riešením nerovnosti (3) bude polrovina, v ktorej sa nachádza testovací bod (na obrázku nižšie čiara L3).

Potom riešime nerovnosť (4) .

Zostrojme hraničnú čiaru z dvoch bodov. Označte čiaru (L4).

Pridajte údaje do hárku programu Excel

Priama čiara (L4) na grafe:

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

Dosadením súradníc bodu (0; 0) dostaneme nerovnosť

Nerovnosť je pravdivá, preto riešením nerovnosti (4) bude polrovina, v ktorej sa nachádza testovací bod (na obrázku vľavo od priamky L4).

Vyriešením dvoch nerovností (5) a (6)

je 1. štvrtina ohraničená súradnicovými čiarami a .

Systém nerovností je vyriešený. Riešením sústavy nerovníc (1) - (6) v tomto príklade je konvexný mnohouholník v ľavom dolnom rohu obrázku ohraničený priamkami L1, L2, L3, L4 a súradnicovými priamkami a . Správny výber polygónu si môžete overiť tak, že do každej nerovnosti pôvodného systému dosadíte testovací bod, napríklad (1; 1). Dosadením bodu (1; 1) dostaneme, že všetky nerovnosti, vrátane prirodzených obmedzení, sú pravdivé.

Zvážte teraz objektívnu funkciu

F= 2X 1 + 3X 2 .

Zostavme úrovňové čiary pre funkčné hodnoty F=0 a F=12(číselné hodnoty sú zvolené ľubovoľne). Pridajte údaje do hárku programu Excel

Čiary úrovne na grafe:

Zostrojme vektor smerov (alebo gradient) (2; 3). Vektorové súradnice sa zhodujú s koeficientmi účelovej funkcie F.

objektívna funkcia- reálna alebo celočíselná funkcia viacerých premenných, ktorá podlieha optimalizácii (minimalizácii alebo maximalizácii) s cieľom vyriešiť nejaký optimalizačný problém. Termín sa používa v matematickom programovaní, operačnom výskume, lineárnom programovaní, teórii štatistického rozhodovania a iných oblastiach matematiky, predovšetkým aplikovaného charakteru, hoci cieľom optimalizácie môže byť aj riešenie samotného matematického problému. Okrem objektívnej funkcie môžu v optimalizačnom probléme podliehať premenným obmedzeniam v podobe systému rovnosti alebo nerovností. Vo všeobecnom prípade môžu byť argumenty objektívnej funkcie špecifikované na ľubovoľných množinách.

Príklady

Hladké funkcie a sústavy rovníc

Problém riešenia ľubovoľnej sústavy rovníc

( 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\((\začiatok(matica)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(matica) )\správny.)

možno formulovať ako problém minimalizácie účelovej funkcie

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

Ak sú funkcie hladké, problém minimalizácie možno vyriešiť gradientovými metódami.

Pre akúkoľvek hladkú účelovú funkciu sa môžeme rovnať 0 (\displaystyle 0) parciálne derivácie vzhľadom na všetky premenné. Optimálna účelová funkcia bude jedným z riešení takéhoto systému rovníc. V prípade funkcie (1) (\displaystyle (1)) to bude systém rovníc najmenších štvorcov (LSM). Akékoľvek riešenie pôvodného systému je riešením systému najmenších štvorcov. Ak je pôvodný systém nekonzistentný, potom systém LSM, ktorý má vždy riešenie, umožňuje získať približné riešenie pôvodného systému. Počet rovníc systému LSM sa zhoduje s počtom neznámych, čo niekedy uľahčuje riešenie spoločných počiatočných systémov.

Lineárne programovanie

Ďalším známym príkladom účelovej funkcie je lineárna funkcia, ktorá sa vyskytuje v problémoch lineárneho programovania. Na rozdiel od kvadratickej účelovej funkcie je optimalizácia lineárnej funkcie možná len vtedy, ak existujú obmedzenia vo forme systému lineárnych rovnosti alebo nerovností.

Kombinatorická optimalizácia

Typickým príkladom kombinatorickej objektívnej funkcie je objektívna funkcia problému obchodného cestujúceho. Táto funkcia sa rovná dĺžke Hamiltonovho cyklu na grafe. Je daný na permutačnej množine n − 1 (\displaystyle n-1) vrcholov grafu a je určený maticou dĺžky hrán grafu. Presné riešenie takýchto problémov často závisí od vymenovania možností.

Kapitola 1. Vyjadrenie hlavného problému lineárneho programovania

1. Lineárne programovanie

Lineárne programovanie je odvetvie matematického programovania, ktoré študuje metódy riešenia extrémnych problémov, ktoré sa vyznačujú lineárnym vzťahom medzi premennými a lineárnym kritériom. Takéto úlohy nachádzajú rozsiahle uplatnenie v rôznych sférach ľudskej činnosti. Systematické štúdium problémov tohto typu sa začalo v rokoch 1939–1940. v dielach L.V. Kantorovič.

K matematickým problémom lineárneho programovania patrí štúdium špecifických výrobných a ekonomických situácií, ktoré sa v tej či onej podobe interpretujú ako problémy optimálneho využívania obmedzených zdrojov.

Rozsah problémov riešených metódami lineárneho programovania je pomerne široký. Sú to napr.

problém optimálneho využitia zdrojov pri plánovaní výroby;

problém zmesí (plánovanie zloženia výrobkov);

problém nájsť optimálnu kombináciu rôznych druhov produktov na skladovanie v skladoch (riadenie zásob resp.);

prepravné úlohy (analýza polohy podniku, pohyb tovaru).

Lineárne programovanie je najrozvinutejšia a najpoužívanejšia časť matematického programovania (okrem toho sem patrí: celočíselné, dynamické, nelineárne, parametrické programovanie). Toto sa vysvetľuje takto:

matematické modely veľkého množstva ekonomických problémov sú lineárne vzhľadom na požadované premenné;

tento typ problémov je v súčasnosti najviac skúmaný. Pre neho boli vyvinuté špeciálne metódy, pomocou ktorých sa tieto problémy riešia, a príslušné počítačové programy;

mnohé problémy lineárneho programovania, ktoré boli vyriešené, našli široké uplatnenie;

niektoré problémy, ktoré v pôvodnej formulácii nie sú lineárne, sa po množstve dodatočných obmedzení a predpokladov môžu stať lineárnymi alebo sa dajú zredukovať do takej podoby, že sa dajú riešiť metódami lineárneho programovania.

Ekonomický a matematický model akéhokoľvek problému lineárneho programovania zahŕňa: objektívnu funkciu, ktorej optimálnu hodnotu (maximum alebo minimum) treba nájsť; obmedzenia vo forme sústavy lineárnych rovníc alebo nerovníc; požiadavka nezápornosti premenných.

Vo všeobecnosti je model napísaný takto:

objektívna funkcia

(1.1) v rámci obmedzení

(1.2) požiadavky na nezápornosť

(1.3) kde X j– premenné (neznáme);

- koeficienty úlohy lineárneho programovania.

Problémom je nájsť optimálnu hodnotu funkcie (1.1) pri obmedzeniach (1.2) a (1.3).

Systém obmedzení (1.2) sa nazýva funkčné obmedzenia problému a obmedzenia (1.3) sa nazývajú priame obmedzenia.

Vektor, ktorý spĺňa obmedzenia (1.2) a (1.3) sa nazýva realizovateľné riešenie (plán) úlohy lineárneho programovania. Plán, pre ktorý funkcia (1.1) dosiahne svoju maximálnu (minimálnu) hodnotu, sa nazýva optimálny.

1.2. Simplexná metóda riešenia úloh lineárneho programovania

Simplexovú metódu vyvinul a prvýkrát použil na riešenie problémov v roku 1947 americký matematik J. Dantzig.

Úlohy dvojrozmerného lineárneho programovania sú riešené graficky. Pre prípad N=3 môžeme uvažovať o trojrozmernom priestore a účelová funkcia dosiahne svoju optimálnu hodnotu v jednom z vrcholov mnohostenu.

Prípustné riešenie (prípustný plán) úlohy LP v štandardnom tvare je usporiadaná množina čísel (x1, x2, ..., xn), ktoré spĺňajú obmedzenia; je bod v n-rozmernom priestore.

Súbor prípustných riešení tvorí oblasť prípustných riešení (SDR) problému LP. ODR je konvexný mnohosten (polygón).

Vo všeobecnosti, keď je do problému zapojených N-neznámych, môžeme povedať, že oblasť uskutočniteľných riešení špecifikovaná systémom obmedzujúcich podmienok je reprezentovaná konvexným mnohostenom v n-rozmernom priestore a optimálnou hodnotou cieľa. funkcia sa dosiahne v jednom alebo viacerých vrcholoch.

Riešenie sa nazýva základné, ak sú všetky voľné premenné rovné nule.

Referenčný roztok je základný nezáporný roztok. Nosný roztok môže byť nedegenerovaný a degenerovaný. Podporné riešenie sa nazýva nedegenerované, ak sa počet jeho nenulových súradníc rovná hodnote systému, inak je degenerované.

Uskutočniteľné riešenie, pri ktorom účelová funkcia dosiahne svoju extrémnu hodnotu, sa nazýva optimálne a označuje sa .

Je veľmi ťažké vyriešiť tieto problémy graficky, keď je počet premenných viac ako 3. Existuje univerzálny spôsob riešenia problémov lineárneho programovania, nazývaný simplexná metóda.

Simplexová metóda je univerzálna metóda na riešenie problémov LP, čo je iteratívny proces, ktorý začína jedným riešením a pri hľadaní najlepšej možnosti sa pohybuje pozdĺž rohových bodov oblasti realizovateľných riešení, kým nedosiahne optimálnu hodnotu. .

Môže sa použiť na riešenie akéhokoľvek problému lineárneho programovania.

Simplexová metóda je založená na myšlienke postupného zlepšovania výsledného riešenia.

Geometrickým významom simplexovej metódy je postupný presun z jedného vrcholu polyhedrónu obmedzenia do susedného, ​​v ktorom má účelová funkcia najlepšiu (alebo aspoň nie najhoršiu) hodnotu, kým sa nenájde optimálne riešenie - vrchol, kde optimálna hodnota je dosiahnutá cieľová funkcia (ak má problém konečné optimum).

Ak teda máme systém obmedzení zredukovaný na kanonickú formu (všetky funkčné obmedzenia sú vo forme rovnosti), nájdeme akékoľvek základné riešenie tohto systému, pričom sa musíme snažiť nájsť ho čo najjednoduchšie. Ak sa prvé nájdené základné riešenie ukázalo ako uskutočniteľné, potom sa skontroluje jeho optimálnosť. Ak to nie je optimálne, potom sa prechádza na iné, nevyhnutne prípustné, základné riešenie. Simplexová metóda zaručuje, že pri tomto novom riešení sa cieľová funkcia, ak nedosiahne optimum, k nej približuje (alebo sa od nej aspoň nevzďaľuje). S novým prípustným základným riešením sa robí to isté, kým sa nenájde riešenie, ktoré je optimálne.

Proces aplikácie simplexovej metódy zahŕňa implementáciu jej troch hlavných prvkov:

metóda na určenie nejakého počiatočného možného základného riešenia problému;

pravidlo prechodu na najlepšie (presnejšie nie najhoršie) riešenie;

kritérium pre kontrolu optimálnosti nájdeného riešenia.

Simplexová metóda zahŕňa množstvo krokov a môže byť formulovaná ako jasný algoritmus (jasná inštrukcia na vykonávanie sekvenčných operácií). To vám umožňuje úspešne ho naprogramovať a implementovať na počítači. Problémy s malým počtom premenných a obmedzení je možné vyriešiť simplexnou metódou manuálne.

6.1 Úvod

Optimalizácia. Časť 1

Metódy optimalizácie vám umožňujú vybrať si najlepšiu možnosť dizajnu zo všetkých možných možností. V posledných rokoch sa týmto metódam venovala veľká pozornosť a v dôsledku toho sa vyvinulo množstvo vysoko účinných algoritmov, ktoré umožňujú nájsť optimálnu možnosť návrhu pomocou digitálneho počítača. Táto kapitola načrtáva základy teórie optimalizácie, uvažuje o princípoch konštrukcie algoritmov pre optimálne riešenia, popisuje najznámejšie algoritmy a analyzuje ich výhody a nevýhody.

6.2 Základy teórie optimalizácie

Pojem „optimalizácia“ v literatúre označuje proces alebo postupnosť operácií, ktoré vám umožňujú získať rafinované riešenie. Hoci konečným cieľom optimalizácie je nájsť najlepšie, alebo „optimálne“ riešenie, človek sa zvyčajne musí uspokojiť skôr s vylepšovaním známych riešení ako s ich zdokonaľovaním. Preto je pravdepodobnejšie, že optimalizácia sa bude chápať ako snaha o dokonalosť, ktorú možno nedosiahne.

Ak vezmeme do úvahy nejaký ľubovoľný systém opísaný m rovníc s n neznámymi, môžeme rozlíšiť tri hlavné typy problémov. Ak m=n, problém sa nazýva algebraický. Takýto problém má väčšinou jedno riešenie. Ak m>n, potom je problém predefinovaný a spravidla nemá žiadne riešenie. Nakoniec pre m

Predtým, ako pristúpime k diskusii o otázkach optimalizácie, uvedieme niekoľko definícií.

Dizajnové parametre

Tento pojem označuje nezávisle premenné parametre, ktoré úplne a jednoznačne definujú riešený konštrukčný problém. Konštrukčné parametre sú neznáme veličiny, ktorých hodnoty sa počítajú počas procesu optimalizácie. Akékoľvek základné alebo odvodené veličiny, ktoré slúžia na kvantitatívne opísanie systému, môžu slúžiť ako parametre návrhu. Takže to môžu byť neznáme hodnoty dĺžky, hmotnosti, času, teploty. Množstvo konštrukčných parametrov charakterizuje stupeň zložitosti tohto konštrukčného problému. Zvyčajne sa počet konštrukčných parametrov označuje n a samotné konštrukčné parametre x so zodpovedajúcimi indexmi. Teda n návrhových parametrov tohto problému budeme označovať

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

objektívna funkcia

Toto je výraz, ktorého hodnotu sa inžinier snaží maximalizovať alebo minimalizovať. Objektívna funkcia umožňuje kvantitatívne porovnať dve alternatívne riešenia. Z matematického hľadiska účelová funkcia opisuje nejakú (n + 1) - rozmernú plochu. Jeho hodnota je určená konštrukčnými parametrami

M=M(x1,x2,...,xn).

Príklady objektívnej funkcie, s ktorými sa často stretávame v inžinierskej praxi, sú náklady, hmotnosť, pevnosť, rozmery, účinnosť. Ak existuje len jeden parameter návrhu, potom účelovú funkciu možno znázorniť krivkou na rovine (obr. 6.1). Ak existujú dva parametre návrhu, potom bude cieľová funkcia reprezentovaná plochou v priestore troch rozmerov (obr. 6.2). Pri troch alebo viacerých parametroch návrhu sa povrchy špecifikované účelovou funkciou nazývajú hyperplochy a nemožno ich zobraziť.

zheniya konvenčné prostriedky. Topologické vlastnosti povrchu cieľovej funkcie hrajú dôležitú úlohu v procese optimalizácie, pretože od nich závisí výber najefektívnejšieho algoritmu.

Objektívna funkcia môže mať v niektorých prípadoch najneočakávanejšie formy. Napríklad nie je vždy možné ho vyjadriť

Obr. 1. Jednorozmerná účelová funkcia.

Obr.6.2.Dvojrozmerná účelová funkcia.

uzavretá matematická forma, v ostatných prípadoch môže

byť po častiach hladká funkcia. Objektívna funkcia môže niekedy vyžadovať tabuľku technických údajov (napríklad tabuľku stavu pary) alebo môže byť potrebné vykonať experiment. V niektorých prípadoch majú parametre návrhu iba celočíselné hodnoty. Príkladom môže byť počet zubov v ozubenom kolese alebo počet skrutiek v prírube. Niekedy majú konštrukčné parametre iba dve hodnoty - áno alebo nie. Kvalitatívne parametre, ako je spokojnosť zákazníka, spoľahlivosť, estetika, sa v procese optimalizácie ťažko zohľadňujú, keďže sa takmer nedajú kvantifikovať. Avšak v akejkoľvek forme je prezentovaná účelová funkcia, musí ísť o jednohodnotovú funkciu parametrov návrhu.

V mnohých optimalizačných problémoch sa vyžaduje zavedenie viac ako jednej objektívnej funkcie. Niekedy môže byť jeden z nich nekompatibilný s druhým. Príkladom je návrh lietadla, kedy sa požaduje poskytnúť maximálnu pevnosť, minimálnu hmotnosť a zároveň minimálne náklady. V takýchto prípadoch musí projektant zaviesť systém priorít a každej účelovej funkcii priradiť nejaký bezrozmerný multiplikátor. V dôsledku toho sa objaví „kompromisná funkcia“, ktorá umožňuje použiť jednu zloženú cieľovú funkciu v procese optimalizácie.

Nájdenie minima a maxima

Niektoré optimalizačné algoritmy sú prispôsobené na nájdenie maxima, iné na nájdenie minima. Bez ohľadu na typ riešeného extrémneho problému je však možné použiť rovnaký algoritmus, pretože problém minimalizácie možno ľahko zmeniť na maximálny problém zmenou znamienka účelovej funkcie na opačný. Táto technika je znázornená na obrázku 6.3.

Dizajnový priestor

Toto je názov oblasti definovanej všetkými n návrhovými parametrami. Dizajnový priestor nie je taký veľký, ako by sa mohlo zdať, pretože je zvyčajne obmedzený na množstvo

stavy spojené s fyzikálnou podstatou problému. Obmedzenia môžu byť také silné, že úloha nebude mať žiadne

Obr.6.3 Zmena znamienka účelovej funkcie na opak

Maximálna úloha sa stáva minimálnou úlohou.

vyhovujúce riešenie. Obmedzenia sa delia do dvoch skupín: obmedzenia – rovnosti a obmedzenia – nerovnosti.

Obmedzenia – rovnosť

Obmedzenia - rovnosti - je závislosť medzi parametrami návrhu, ktoré je potrebné vziať do úvahy pri hľadaní riešenia. Odrážajú prírodné zákony, ekonomiku, práva, prevládajúci vkus a dostupnosť potrebných materiálov. Počet obmedzení – rovnosti môže byť ľubovoľný. Vyzerajú ako

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

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

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

Cj(x1,x2,...,xn)=0.

Ak sa niektorý z týchto vzťahov dá vyriešiť s ohľadom na jeden z parametrov návrhu, potom vám to umožní vylúčiť tento parameter z procesu optimalizácie. Tým sa znižuje počet rozmerov konštrukčného priestoru a zjednodušuje sa riešenie problému.

Obmedzenia – nerovnosti

Ide o špeciálny druh obmedzenia vyjadreného nerovnosťami. Vo všeobecnosti ich môže byť ľubovoľný počet a všetky majú tvar

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 si uvedomiť, že veľmi často sa kvôli obmedzeniam nedosiahne optimálna hodnota účelovej funkcie tam, kde má jej povrch nulový gradient. Často je najlepšie riešenie na jednej z hraníc domény dizajnu.

Lokálne optimum

Toto je názov bodu v dizajnovom priestore, v ktorom má účelová funkcia najväčšiu hodnotu v porovnaní s jej hodnotami vo všetkých ostatných bodoch v jej bezprostrednom susedstve.

6.4 Ľubovoľná účelová funkcia môže mať niekoľko

lokálne optimálna.

Na obr. Obrázok 6.4 ukazuje jednorozmernú účelovú funkciu, ktorá má dve lokálne optimá. Dizajnový priestor často obsahuje mnoho lokálnych optim a je potrebné dbať na to, aby sa prvé nepomýlilo s optimálnym riešením problému.

Globálne optimálne

Globálne optimum je optimálnym riešením pre celý dizajnový priestor. Je to lepšie ako všetky ostatné riešenia zodpovedajúce lokálnemu optimu a to je to, čo dizajnér hľadá. Je možný prípad niekoľkých rovnakých globálnych optím umiestnených v rôznych častiach dizajnového priestoru. Ako je problém s optimalizáciou položený najlepšie ilustruje príklad.

Príklad 6.1

Nech je potrebné navrhnúť obdĺžnikový kontajner s objemom 1 m, určený na prepravu nebaleného vlákna. Je žiaduce, aby sa na výrobu takýchto nádob vynaložilo čo najmenej materiálu (za predpokladu konštantnej hrúbky steny to znamená, že plocha by mala byť minimálna), pretože to bude lacnejšie. Aby bolo pohodlné prepravovať kontajner vysokozdvižným vozíkom, jeho šírka musí byť aspoň 1,5 m.

Sformulujme tento problém vo forme vhodnej na aplikáciu optimalizačného algoritmu.

Konštrukčné parametre: x 1 , x 2 , x 3 .

Cieľovou funkciou (ktorú je potrebné minimalizovať) je plocha bočného povrchu nádoby:

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

Obmedzenie – rovnosť:

Objem \u003d x 1 x 2 x 3 \u003d 1 m3.

Obmedzenie - nerovnosť:

Problémy lineárneho programovania

Lineárne programovanie (LP) je jednou zo sekcií matematického programovania - disciplíny, ktorá študuje extrémne (optimalizačné) problémy a vyvíja metódy na ich riešenie.

Problém s optimalizáciou je matematický problém, ktorý spočíva v nájdení optimálnej (t.j. maximálnej alebo minimálnej) hodnoty účelovej funkcie, pričom hodnoty premenných musia patriť do určitej oblasti prípustných hodnôt (ODV).

Vo všeobecnosti formulácia extrémneho problému matematického programovania spočíva v určení najväčšej alebo najmenšej hodnoty funkcie, tzv. objektívna funkcia, za podmienok (obmedzení) , kde a sú dané funkcie a sú dané konštanty. Obmedzenia v podobe rovnosti a nerovností zároveň určujú množinu (región) realizovateľných riešení (ODS), a sú tzv. konštrukčné parametre.

V závislosti od typu funkcií a problémov matematického programovania sú rozdelené do niekoľkých tried (lineárne, nelineárne, konvexné, celočíselné, stochastické, dynamické programovanie atď.).

AT všeobecný pohľad Problém LP má nasledujúcu formu:

, (5.1)

, , (5.2)

, , (5.3)

kde , , sú dané konštanty.

Funkcia (5.1) sa nazýva účelová funkcia; systémy (5.2), (5.3) - systémom obmedzení; podmienka (5.4) je podmienka nezápornosti návrhových parametrov.

Súbor parametrov návrhu vyhovujúcich obmedzeniam (5.2), (5.3) a (5.4) sa nazýva prijateľné riešenie alebo plánovať.

Optimálne riešenie alebo optimálny plánÚloha LP sa nazýva uskutočniteľné riešenie, v ktorom cieľová funkcia (5.1) nadobúda optimálnu (maximálnu alebo minimálnu) hodnotu.

Štandardná úloha LP sa nazýva problém nájdenia maximálnej (minimálnej) hodnoty účelovej funkcie (5.1) za podmienky (5.2) a (5.4), kde , , t.j. tie. obmedzenia iba vo forme nerovností (5.2) a všetky parametre návrhu spĺňajú podmienku nezápornosti a neexistujú žiadne podmienky vo forme rovnosti:

,

, , (5.5)

.

Kanonická (hlavná) úloha LP sa nazýva problém nájdenia maximálnej (minimálnej) hodnoty účelovej funkcie (5.1) za podmienky (5.3) a (5.4), kde , , t.j. tie. obmedzenia iba vo forme rovnosti (5.3) a všetky parametre návrhu spĺňajú podmienku nezápornosti a neexistujú žiadne podmienky vo forme nerovností:

,

.

Kanonický problém LP možno zapísať aj v maticovej a vektorovej forme.

Maticová forma kanonického problému LP má nasledujúci tvar:

Vektorová forma kanonického problému LP.