objektívna funkcia ako. Cieľová funkcia a jej formy. Problémy lineárneho programovania

Účelová funkcia je matematickým vyjadrením závislosti kritéria optimality na požadovaných premenných.

2. Gradientová funkcia.

Vektor, ktorého komponenty sú hodnoty parciálnych derivácií, teda vektor

sa nazýva gradient funkcie vypočítaný v bode.

3. Všeobecný problém lineárneho programovania.

Štandardná matematická formulácia všeobecného problému lineárne programovanie vyzerá takto: musíte nájsť extrémnu hodnotu ukazovateľa výkonu (objektívna funkcia)

(lineárna funkcia prvkov riešenia) za lineárnych obmedzujúcich podmienok kladených na prvky riešenia:

kde sú uvedené čísla.

4. Štandardný problém s lp.

Vo svojej štandardnej forme je problém lineárneho programovania maximálny (minimálny) problém pre lineárnu účelovú funkciu. Jeho systém obmedzení pozostáva z jedného lineárne nerovnosti typ "<= » или « >= ". Všetky premenné úlohy sú nezáporné.

Akýkoľvek problém lineárneho programovania môže byť formulovaný z hľadiska štandardná forma. Transformácia minimálneho problému na maximálny problém, ako aj zabezpečenie nezápornosti premenných, sa uskutočňuje rovnakým spôsobom ako predtým. Akákoľvek rovnosť v systéme obmedzení je ekvivalentná systému vzájomne opačných nerovností:

Sú aj iné spôsoby, ako transformovať systém rovnosti na systém nerovností, t.j. akýkoľvek problém lineárneho programovania môže byť formulovaný v štandardnej forme.

2 možnosti odpovede:

Štandardný problém s LP. alebo, v maticovom zápise, kde je matica koeficientov. Vektor sa nazýva vektor koeficientov lineárneho tvaru, vektor obmedzenia.

5. Kanonický problém lp.

AT kanonickej podobe problém je problém pre maximum (minimum) nejakej lineárnej funkcie F , jeho systém obmedzení pozostáva len z rovníc (rovníc). Zároveň premenné úlohy X 1 , X 2 , ..., X n sú nezáporné:

Komu kanonickej podobe môžete transformovať akýkoľvek problém lineárneho programovania.

Krátky vstup kanonický problém LP:

X = (x1, x2, ..., xn), C = (c1, c2, ..., cn).

2 možnosti odpovede:

Kanonický problém LP. alebo v maticovom zápise,

6. Symetrické a asymetrické duálne úlohy.

Duálny problém lineárneho programovania. Zvážte problém LP (1) alebo v maticovom zápise (2) Problém duálny k (1) (duálny problém) je problém LP v premenných (3) alebo v maticovom zápise (4) kde . Pravidlá pre zostavenie úlohy (3) podľa formy písania úlohy (1) sú nasledovné: v úlohe (3)

v matici úloh je toľko premenných, koľko je riadkov (1). Matica obmedzení v (3) je transportovaná matica. Vektor pravej strany obmedzení v (3) slúži ako vektor koeficientov lineárneho tvaru maximalizovaného v (1), pričom znamienka nerovností sa menia na rovnosť. Naopak, účelová funkcia v (3) je lineárna forma, ktorej koeficienty sú dané vektorom pravej strany obmedzení problému (1), pričom maximalizácia sa mení na minimalizáciu. Podmienka nezápornosti sa uplatňuje na duálne premenné. Problém (1), na rozdiel od duálny problém(3) sa nazýva priamka. Veta o dualite. Ak sú prípustné vzájomne duálne úlohy (2), (4), potom majú obidva riešenie a rovnakú hodnotu.

Symetrické duálne problémy

Akýsi duál lineárne, programovanie sú duálne symetrické problémy, v ktorých je systém obmedzení pôvodného aj duálneho problému daný nerovnosťami a na duálne premenné je kladená podmienka nezápornosti.

objektívna funkcia

Funkcia, ktorá spája cieľ (optimalizovanú premennú) s riadenými premennými v optimalizačnom probléme.

Je dôležité, aby sa kritérium vždy zavádzalo zvonku a až potom sa hľadá rozhodovacie pravidlo, ktoré minimalizuje alebo maximalizuje cieľovú funkciu.

pozri tiež

• Burak Ya. I., Ogirko IV Optimálny ohrev valcového plášťa s teplotne závislými materiálovými charakteristikami // Mat. metódy a fiz.-mekh. poliach. - 1977. - Vydanie. 5. - S.26-30

Nadácia Wikimedia. 2010.

• Ústredný výskumný ústav robotiky a technickej kybernetiky
• 1885 v divadle

Pozrite sa, čo je „Objective Function“ v iných slovníkoch:

objektívna funkcia- — [Ya.N. Luginsky, M.S. Fezi Zhilinskaya, Yu.S. Kabirov. Anglický ruský slovník elektrotechniky a energetiky, Moskva, 1999] cieľová funkcia V extrémnych problémoch funkcia, ktorej minimum alebo maximum treba nájsť. To……

objektívna funkcia- pri extrémnych problémoch je potrebné nájsť funkciu, ktorej minimum alebo maximum. Toto je kľúčový koncept optimálne programovanie. Po nájdení extrému C.f. a teda určením hodnôt riadených premenných, ktoré sú k nemu ... ...

objektívna funkcia- 3.1.8 obchodná funkcia súbor procesov na dosiahnutie špecifického obchodného cieľa Zdroj: R 50.1.041 2002: Infor… Slovník-príručka termínov normatívnej a technickej dokumentácie

objektívna funkcia- tikslo funkcie statusas T sritis automatika atitikmenys: angl. objektívna funkcia vok. Zielfunktion, f rus. cieľová funkcia, f; objektívna funkcia, fprac. fonction de cible, f … Automatikos terminų žodynas

objektívna funkcia- funkcia, ktorej extrémna hodnota sa hľadá na prípustnej množine v problémoch matematického programovania(Pozri Matematické programovanie) … Veľká sovietska encyklopédia

OBJEKTÍVNA FUNKCIA- cieľová funkcia je názov funkcie, ktorá sa optimalizuje v úlohách matematického programovania ... Matematická encyklopédia

objektívna funkcia- (podmienené meno, relatívne správne sa dá použiť iba na systémy vytvorené na konkrétny účel osobou), neexistuje v objektívnom svete, existuje systémotvorný faktor ... Teoretické aspekty a základy ekologického problému: interpret slov a idiomatických výrazov

Funkcia cieľovej spotreby- 1. Tento pojem, ako aj viaceré ekvivalentné alebo takmer ekvivalentné (funkcia životnej úrovne, funkcia blahobytu, funkcia spoločenskej užitočnosti, funkcia spotreby atď.) sa označujú v ... ... Ekonomický a matematický slovník

cieľová funkcia spotreby- 1. Tento pojem, ako aj viaceré ekvivalentné alebo takmer ekvivalentné (funkcia životnej úrovne, funkcia blahobytu, funkcia sociálneho úžitku, funkcia spotreby atď.) označujú cieľovú funkciu v teoretických štúdiách ... ... Technická príručka prekladateľa

objektívna funkcia automatizovaného medicínskeho systému- cieľová funkcia AMS Súbor úkonov automatizovaného medicínskeho systému, ktorý zabezpečuje efektívnu realizáciu daného medicínskeho programu. [GOST 27878 88] Témy systému a medicínskych komplexov Zovšeobecňujúce pojmy systému a ... ... Technická príručka prekladateľa

knihy

• Prístup k organizácii adaptívneho systému riadenia učenia založeného na využívaní informačných technológií, A. V. Anastas'in. Otázka použitia informačných technológií v vzdelávací proces vyššie vzdelávacie inštitúcie sa už dlho a neustále diskutuje na rôznych úrovniach. Je to spôsobené rýchlym...

Lineárne programovanie.

Stručný teoretické informácie

Určiť si ciele

Riešenie problému priameho lineárneho programovania odpovedá na nasledujúcu otázku:

v akej intenzite n ziskové procesy (poskytovanie rôznych služieb, výrobné procesy), ktoré používajú m druhov zdrojov (výrobných faktorov) so známymi hraničnými intenzitami využitia týchto zdrojov, výnosy z predaja (zisk) budú maximálne vtedy, keď intenzita spotreby každého zdroja a intenzita zisku (výnosu) v každom z procesov lineárne závisia od intenzity tohto procesu.

Riešenie jeho dvojitého problému odpovedá na nasledujúcu otázku:

pri čom najnižšie ceny na jednotku zdroja bude pre ekonomického agenta nerentabilné ďalej rozširovať proces dosahovania zisku získavaním nových objemov zdrojov, ktorých je v súčasných podmienkach ekonomickej činnosti málo.

Priamy problém lineárneho programovania možno spojiť s nasledujúcou situáciou. K dispozícii n spôsoby dosiahnutia zisku (poskytovanie n typy služieb) s objemami x i (počet kusov i poskytnuté služby). Zároveň využívajú m druhy zdrojov, zásoby j -tá z toho sa rovná b j . Zároveň spotreba každého zdroja j a výšku zisku v každom z procesov i lineárne závisí od počtu poskytnutých služieb i -tý typ s koeficientmi a ji a c i , resp. Matrix ALE=(a ji )m ' n významovo je podobná tej z prvej časti a nazýva sa aj matica technologických, prípadne štruktúrnych koeficientov. Potom je možné získať optimálny plán podľa kritéria maximalizácie zisku vyriešením nasledujúceho problému priameho lineárneho programovania:

Tento problém môže byť spojený s rozšírenou maticou nasledujúceho tvaru:

(4.1)

Problém dual to problem (4) má nasledujúcu formu ( zj – požadované hraničné ceny):

Pri tejto formulácii duálneho problému vyplývajú (5.1) a (5.3) z podmienky minimalizácie cien a z podmienky nerentabilnosti pokračujúcich činností priamo vyplýva podmienka previsu alebo rovnosti nákladov nad výnosmi z predaja.

Základné pojmy modelu

Riešenie (plán, program) - súbor, vektor konkrétnych hodnôt všetkých variabilné parametre riadenie modelu - hodnoty, ktoré je možné zmeniť podľa vôle správcu objektu modelovania. Riešenia sú prípustné (realizovateľné v praxi), neprijateľné (nerealizovateľné kvôli obmedzeniam existujúcim v modeli) a optimálne (najlepšie z prípustných).

objektívna funkcia L(x) – matematický výraz prepojenie faktorov (parametrov) modelu. ekonomický zmysel objektívna funkcia odráža kritérium optimálnosti- ukazovateľ, ktorý má ekonomický obsah a slúži ako formalizácia konkrétneho cieľa riadenia, napríklad: maximalizácia zisku (riadok 1 v (4)), maximalizácia kvality produktu alebo minimalizácia nákladov (5.1).

Reštrikčný systém modely sú limity, ktoré obmedzujú prípustná plocha(prijateľné, uskutočniteľné) rozhodnutia, upevnenie hlavného vnútorného a vonkajšie vlastnosti objekt spojený s cieľom optimalizácie. Komunikačné rovnice(typ f j (x) ) je matematická formalizácia systému obmedzení (riadky 2 a 3 v (4), (5.2, 5.3)). Systém obmedzení odráža ekonomický význam rovníc obmedzenia.

Systém pozostávajúci z objektívnych funkcií a komunikačných rovníc, - problém ekonomického a matematického modelovania (EMM). V prípade, že cieľová funkcia a rovnice spojenia sú lineárne a riadiace premenné sa neustále menia, problém EMM sa nazýva problém lineárneho programovania (LP). Hlavnou vlastnosťou súboru prípustných plánov (MPS) problému LP je, že ide o konvexný mnohosten. Množina sa nazýva konvexná, ak obsahuje všetky segmenty spájajúce akékoľvek dva body tejto množiny. Ak má problém LP riešenie, potom je na vrchole MDP. Plány umiestnené na vrcholoch MDP sa nazývajú základné. Problémy lineárneho programovania sa delia na problémy s obmedzeniami vo forme nerovností (všeobecný problém LP) a vo forme rovnosti (kanonický problém LP). S matematickou formalizáciou ekonomických problémov pomocou lineárneho modelu sa získajú všeobecné úlohy LP - napríklad (4), (5). Akýkoľvek všeobecný problém môže byť spojený s kanonickým problémom zavedením ďalších premenných. Takže, k problému (4), zavedením do každej nerovnosti typu „spotreba zdrojov £ rezerva zdrojov“ (riadok 2 v (4)) dodatočnú premennú xn+j (nepoužitý zostatok j -tý zdroj) je namapovaný na nasledujúci kanonický:

Zároveň sa zvýšila dimenzia problému (6) - počet návrhových premenných - v porovnaní s (4). n predtým n+m .

Pri riešení úlohy (4) majú veľký význam koeficienty návratnosti zdrojov, medzi ktorými sa tu budú používať diferenciálne a prírastkové. Diferenciálny koeficient návratnosti zdrojov k ji zobrazuje náklady poskytnuté pri použití jednotky j - zdroj i služby. Tie typy služieb, pre ktoré všetky k ji sú najmenšie pre všetky typy služieb, sú najmenej ziskové. V optimálnom pláne by nemali byť prítomné. To umožňuje pomocou núteného nulovania objemov poskytovaných služieb zmenšiť rozmer problému a tým zjednodušiť jeho riešenie. Sú vypočítané nasledujúcim spôsobom - k ji =c i /a ji .

prírastkový koeficient návratnosti zdrojov K j je koeficient úmernosti medzi prírastkom hodnoty účelovej funkcie optimálneho plánu a zmenou zásob, ktorá tento prírastok spôsobila j - zdroj. Dá sa to považovať Komu j ukázať, o koľko sa zvýši hodnota objektívnej funkcie pôvodného problému v optimálnom pláne so zvýšením marže j -tý zdroj na jednotku. Z matematického hľadiska je to celková derivácia optimálnej hodnoty účelovej funkcie vzhľadom na maržu j - zdroj: Komu j = dLopt/dbj .

Premenné úlohy

Zostavme si model úloh.

Riešenie

Pred zostavením matematického modelu problému ᴛ.ᴇ. na zapísanie pomocou matematických symbolov je mimoriadne dôležité jasne pochopiť ekonomickú situáciu opísanú v podmienke. Na to je mimoriadne dôležité z hľadiska ekonómie, a nie matematiky, odpovedaj na nasledujúce otázky:

1) Aké sú požadované hodnoty problému?

2) Aký je účel riešenia? Aký parameter úlohy slúži ako kritérium pre efektívnosť (optimálnosť) riešenia, napríklad zisk, náklady, čas atď. Akým smerom by sa mala hodnota tohto parametra meniť (smerom k max alebo k min), aby sa dosiahli najlepšie výsledky?

3) Aké podmienky musia byť splnené vzhľadom na požadované množstvá a zdroje úlohy?

Tieto podmienky stanovujú, ako by mali rôzne parametre úlohy navzájom súvisieť, napríklad množstvo zdroja vynaloženého na výrobu a jeho zásoby v sklade; množstvo vyrobených výrobkov a kapacita skladu, kde budú uskladnené; množstvo vyrobených produktov a dopyt na trhu po týchto produktoch atď.

Až po ekonomickej odpovedi na všetky tieto otázky možno začať zapisovať tieto odpovede v matematickej forme, ᴛ.ᴇ. napísať matematický model.

Úlohou je určiť, koľko farby z každého druhu vyrobiť. Z tohto dôvodu požadované množstvá, a teda aj premenné problému, sú denné objemy výroby každého typu farby:

x1 – denný objem výroby farby 1. druhu, [tony farby/deň];

x2 – denný objem výroby farby 2. druhu, [tony farby/deň].

V podmienke úlohy je formulovaný cieľ – dosiahnuť maximálny príjem z predaja produktov. Tie. kritériom efektívnosti je parameter denného príjmu, ktorý by mal smerovať k maximu. Pre výpočet výšky denného príjmu z predaja farieb oboch typov je mimoriadne dôležité poznať objemy výroby farieb, ᴛ.ᴇ. x1 a x2 ton farby za deň, ako aj veľkoobchodné ceny farieb 1. a 2. typu - podľa stavu 3 a 2 000 rubľov. na 1 tonu farby. Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, príjem z predaja denného objemu výroby farby 1. druhu je 3 x 1 tisíc rubľov. za deň a z predaja farby 2. typu - 2x 2 000 rubľov. za deň. Z tohto dôvodu objektívnu funkciu píšeme ako súčet príjmov z predaja farieb 1. a 2. druhu (za predpokladu, že objemy predaja každej z farieb sú nezávislé)

Cieľová funkcia - pojem a typy. Klasifikácia a vlastnosti kategórie "Cieľová funkcia" 2017, 2018.

- Základné pojmy. Kritériá účinnosti. objektívna funkcia

KAPITOLA 16. OTÁZKY KONTROLY EFEKTÍVNOSTI MANAŽMENTU 1. Čo vyvolalo potrebu zahraničnej ekonomickej aktivity podniku? 2. Čo podporuje zahraničnú ekonomickú aktivitu podniku? 3. Čo je prekážkou ... .

- V našom príklade má účelová funkcia tvar

F(X) = 75X1 + 800/X1 + 78X2 + 1600/X2. Funkcia je konvexná, ak F "(x)>0 pre ľubovoľné x. Skontrolujme: ; ; ; . Funkcia je teda konvexná, pretože "x>0. Problémom sa preto ukazuje výber optimálneho počtu vlakov na dvoch úsekoch konvexné programovanie, čo sa dá vyriešiť....

- Cieľová funkcia spotreby a modelovanie spotrebiteľského správania

V podmienkach trhového systému riadenia výrobných a marketingových aktivít podnikov a firiem sú ekonomické rozhodnutia založené na trhových informáciách a platnosť rozhodnutí je kontrolovaná trhom pri predaji tovarov a služieb. S týmto prístupom...

Definícia. Akékoľvek riešenie systému obmedzení sa nazýva prípustné riešenie LLP.
Definícia. Uskutočniteľné riešenie, pri ktorom účelová funkcia dosiahne svoje maximum resp minimálna hodnota, sa nazýva optimálne riešenie.

Na základe týchto definícií môže byť problém LP formulovaný nasledovne: spomedzi všetkých bodov konvexnej oblasti, ktorá je riešením systému obmedzení, vyberte ten, ktorého súradnice sú minimalizované (maximalizované) lineárna funkcia F = s 1 X + s 2 r.
Všimnite si, že premenné X, r v LLP majú spravidla nezáporné hodnoty ( X≥ 0, r≥ 0), takže oblasť sa nachádza v prvej štvrtine súradnicovej roviny.

Zvážte lineárnu funkciu F = s 1 X + s 2 r a opraviť nejakú hodnotu F. Nech napr. F= 0, t.j. s 1 X + s 2 r= 0. Grafom tejto rovnice bude priamka prechádzajúca počiatkom (0; 0) (obr.).
Obrázok
Pri zmene tejto pevnej hodnoty F = d, rovný s 1 X+ s 2 y=d sa bude pohybovať rovnobežne a "nakreslí" celú rovinu. Nechaj D- polygón - oblasť riešenia systému obmedzení. Keď sa to zmení d rovno s 1 X + s 2 r = d, za nejakú hodnotu d = d 1 dosiahne polygón D, nazvime tento bod ALE"vstupný bod" a potom po prejdení polygónu pri určitej hodnote d = d 2 budeme mať s ním posledného spoločný bod AT, zavoláme si AT„výstupný bod“.
Je zrejmé, že jeho najmenší a najväčšiu hodnotu objektívna funkcia F=s 1 X + s 2 r dosah na vstupné body ALE a "exit" AT.
Vzhľadom na to optimálna hodnota na množine realizovateľných riešení má účelová funkcia vrcholy oblasti D, môžeme navrhnúť nasledujúci plán riešenia LLP:

1. zostrojte doménu riešenia systému obmedzení;
2. zostrojte priamku zodpovedajúcu cieľovej funkcii a paralelným prekladom tejto priamky nájdite bod „vstupu“ alebo „výstupu“ (v závislosti od požiadavky minimalizovať alebo maximalizovať účelovú funkciu);
3. určiť súradnice tohto bodu, vypočítať v nich hodnotu účelovej funkcie.

Všimnite si, že vektor ( s 1 , s 2), kolmo na priamku, ukazuje smer rastu cieľovej funkcie.

S grafikou PLP rozhodnutie Existujú dva prípady, ktoré si vyžadujú osobitnú diskusiu.

Prípad 1
Obrázok 6
Pri priamom pohybe s 1 X + s 2 r= d"vstup" alebo "výstup" (ako na obrázku) nastane pozdĺž strany mnohouholníka. Toto sa stane, ak má mnohouholník strany rovnobežné s čiarou. s 1 X+ s 2 pri = d .
V tomto prípade existuje nekonečný počet „výstupných“ („vstupných“) bodov, konkrétne akýkoľvek bod segmentu AB. To znamená, že účelová funkcia nadobúda maximálnu (minimálnu) hodnotu nie v jednom bode, ale vo všetkých bodoch ležiacich na zodpovedajúcej strane mnohouholníka. D.

Prípad 2
Zvážte prípad, keď je rozsah prípustných hodnôt neobmedzený.
V prípade neobmedzenej oblasti môže byť účelová funkcia špecifikovaná tak, že jej zodpovedajúca čiara nemá „výstupný“ (alebo „vstupný“) bod. Vtedy sa nikdy nedosiahne maximálna hodnota funkcie (minimum) - hovoria, že funkcia nie je obmedzená.
Obrázok
Je potrebné nájsť maximálnu hodnotu účelovej funkcie F = 4X + 6r→ max , so systémom obmedzení
Zostrojme doménu prípustných riešení, t.j. graficky vyriešiť systém nerovností. Aby sme to urobili, zostrojíme každú priamku a definujeme polroviny dané nerovnicami.
X + r = 18

X	12	9
r	6	9

0,5X + r = 12

X	12	18
r	6	3

X= 12 - rovnobežne s osou OY ;
r= 9 - rovnobežne s osou VÔL ;
X= 0 - os OY ;
r = 0 - os VÔL;
X≥ 0 – polrovina napravo od osi OY;
r≥ 0 – polrovina nad osou VÔL;
r≤ 9 - nižšie v polovičnej rovine r = 9;
X ≤ 12 - polrovina vľavo X = 12;
0,5X + r≤ 12 - polrovina pod priamkou 0,5 X + r = 12;
X + r≤ 18 - polrovina pod priamkou X + r = 18.
Obrázok
Priesečníkom všetkých týchto polrovín je zrejme päťuholník OAVSD, s vrcholmi v bodoch O(0; 0), ALE(0; 9), AT(6; 9), OD(12; 6), D(12; 0). Tento päťuholník tvorí oblasť realizovateľných riešení problému.

Zvážte objektívnu funkciu problému F = 4X + 6r→ max.

X	3	0
r	–2	0

Zostrojme priamku zodpovedajúcu hodnote funkcie F = 0: 4X + 6r= 0. Túto čiaru budeme posúvať paralelne. Z celej rodiny línií 4 X+ 6r= const posledný vrchol, cez ktorý čiara prechádza, keď ide za hranicu polygónu, bude vrcholom OD(12; 6). Je to v nej F = 4X + 6r dosiahne svoje maximálna hodnota.
Takže, o X = 12, r= 6 funkcia F dosiahne svoju maximálnu hodnotu F= 4 ∙ 12 + 6 ∙ 6 = 84, rovná sa 84. Bod so súradnicami (12; 6) spĺňa všetky nerovnosti systému obmedzení a hodnota účelovej funkcie v ňom je optimálna. F* = 84 (optimálna hodnota bude označená „*“).
Problém je vyriešený. Je teda potrebné vyrobiť 12 produktov typu I a 6 produktov typu II, pričom zisk bude 84 tisíc rubľov.

Grafická metóda sa používa na riešenie problémov, ktoré mali v systéme obmedzení iba dve premenné. Túto metódu je možné aplikovať aj na systémy nerovností s tromi premennými. Geometricky bude situácia iná, úlohu priamok budú hrať roviny v trojrozmernom priestore a riešením nerovnosti v troch premenných bude polopriestor umiestnený na jednej strane roviny. Úlohu regiónov budú zohrávať mnohosteny, ktoré sú priesečníkom polpriestorov.