Sarcină programare liniară este găsirea minimului unei funcții liniare f: n > 1 definit pe o mulțime convexă închisă care se distinge prin inegalități liniare.
Problemă generală a programării liniare se pare ca:
Dat un sistem m ecuatii lineareși inegalități cu n variabile
și funcția liniară F = c 1 x 1 + c 2 x 2 +… + c n x n min (max)
Sistemul (1) se numește sistem de constrângeri, iar funcția F este numită funcție liniară, formă liniară, funcție obiectivă sau funcție de obiectiv.
Mai pe scurt sarcină comună programarea liniară poate fi reprezentată ca:
x=(x|Axb, A=, b=( T )}
Problema programării liniare este scrisă și sub alte forme - canonice și normale. Sarcina canonică este denumirea Zk, să numim următoarele:
x=(x|Axb, ?0, j=))
O problemă normală este notația Zn, să numim astfel
x=(x|Axb, ?0, j=))
Seturi și funcții convexe
Definiția unei mulțimi convexe: o mulțime este convexă dacă, împreună cu oricare două puncte, mulțimea conține toate punctele segmentului care leagă un punct cu un punct din spațiu.
Următoarea figură prezintă două seturi în plan, unul este convex și celălalt nu.
Orez. 1
Convexe în spațiu sunt, de exemplu, astfel de mulțimi: întregul spațiu, octantul său pozitiv și octantul nenegativ, orice bilă, atât deschisă, cât și închisă, orice hiperplan (dat de o ecuație a formei, precum și jumătatea deschisă și închisă). -spaţii, date, respectiv, de condiţiile şi.
Printre punctele unei mulțimi convexe, se pot evidenția punctele interioare, de limită și de colț.
Punctul mulțimii se numește intern, dacă o parte din vecinătatea sa conține puncte doar din acest set.
Punctul mulțimii se numește graniță, dacă oricare dintre vecinătățile sale conține atât puncte care aparțin mulțimii date, cât și puncte care nu îi aparțin.
Punctele de colț sunt de interes deosebit în problemele de programare liniară. Se numește punctul mulțimii unghiular(sau extremă) dacă nu este intern pentru niciun segment care aparține în întregime mulțimii date.
Pe fig. exemple diverse puncte poligon: interior (punctul M), hotar (punctul N) și colț (punctele A, B, C, D, E). Punctul A este unghiular, deoarece pentru orice segment care aparține în întregime poligonului, de exemplu, segmentul AP, nu este intern; punctul A este intern segmentului KL, dar acest segment nu aparține în întregime poligonului.
Pentru o mulțime convexă, punctele de colț coincid întotdeauna cu vârfurile poligonului (poliedrul), în timp ce acest lucru nu este necesar pentru o mulțime neconvexă. Un set de puncte se numește închis dacă include toate punctele sale limită. Setul de puncte este numit limitat, dacă există o bilă (cerc) de rază de lungime finită centrată în orice punct al mulțimii care conține complet mulțimea dată; în caz contrar, mulțimea se numește nemărginită. Mulțime închisă convexă de puncte ale planului, având un număr finit puncte de colt, se numește poligon convex, dacă este mărginită, și o regiune poligonală convexă, dacă este nemărginită.
O funcție f: se numește convexă dacă epigraful ei epi f= este o mulțime convexă. Figura prezintă o funcție convexă, graficul acesteia este evidențiat cu albastru, iar supragraful este colorat în verde.
O funcție f: se numește închisă dacă epigraful ei este o mulțime închisă.
Semnificația geometrică a soluțiilor inegalităților, ecuațiilor și sistemelor acestora
Să luăm în considerare soluțiile inegalităților.
Enunțul 1. Mulțimea soluțiilor inegalității cu două variabile a11x1+a12x2<=b1 является одной из двух полуплоскостей, на которые вся плоскость делится прямой a11x1+a12x2=b1, включая и эту прямую, а другая полуплоскость с той же прямой есть множество решений неравенства a11x1+a12x2>=b1.
Pentru a determina semiplanul dorit (superior sau inferior), se recomandă setarea unui punct de control arbitrar care nu se află pe limita sa - linia construită. Dacă inegalitatea este satisfăcută la un punct de control, atunci este satisfăcută și în toate punctele semiplanului care conține punctul de control și nu este satisfăcută în toate punctele celuilalt semiplan. Și invers, dacă inegalitatea nu este satisfăcută la punctul de control, aceasta nu este satisfăcută în toate punctele semiplanului care conține punctul de control și este satisfăcută în toate punctele celuilalt semiplan. Ca punct de control, este convenabil să luăm originea coordonatelor O (0; 0), care nu se află pe linia construită.
Luați în considerare setul de soluții ale sistemelor de inegalități.
Enunțul 2. Mulțimea soluțiilor sistemului de îmbinări m inegalități liniare cu două variabile este un poligon convex (sau o zonă poligonală convexă).
Fiecare dintre inegalități, în conformitate cu afirmația 1, definește unul dintre semiplanuri, care este un set convex de puncte. Mulțimea soluțiilor unui sistem comun de inegalități liniare sunt puncte care aparțin semiplanurilor de soluții ale tuturor inegalităților, adică. aparțin intersecției lor. Conform declarației de intersecție multimi convexe această mulțime este convexă și conține un număr finit de puncte de colț, adică este un poligon convex (o zonă poligonală convexă).
Coordonatele punctelor de colț - vârfurile poligonului se găsesc ca coordonatele punctelor de intersecție ale liniilor corespunzătoare.
La construirea zonelor de soluții pentru sisteme de inegalități pot apărea și alte cazuri: mulțimea soluțiilor este o regiune poligonală convexă (Fig. a); un punct (fig. b); o mulţime goală când sistemul de inegalităţi este inconsecvent (fig. c).
Definirea conceptului de dualitate folosind transformarea Legendre
Fie f:. Funcția f*: definită de egalitatea f*(x*)==(x*) se numește funcție adjunctă la f, iar funcția f**: definită de regula f**(x*)==( x*) se numește a doua funcție adjunctă la f.
Maparea f* (x*) =< x*, x>? f(x) se numește transformată Legendre.
Tehnica obișnuită pentru construirea unei probleme duale este următoarea. Problema de minimizare
unde X este un spațiu liniar, este inclus în clasa de probleme similare cu acesta, în funcție de parametru:
unde Y este un alt spațiu liniar, F (x, 0)=f(x) (funcția F se numește perturbarea lui f). De obicei, se presupune că F este convex. Dualul problemei cu privire la o perturbație dată se numește. sarcină
unde F* este o funcție duală (conjugată) la F în sensul lui Legendre - Young - Fenchel. O astfel de dualitate ne permite să asociem cu fiecare funcție convexă f: X-> R un obiect dual - funcția adjunctă definită pe spațiul dual X* și definită prin formula
Pentru cele mai simple probleme de programare convexă, cum ar fi
unde X este un spațiu liniar, funcții convexe pe X, set B-convexîn X (cazurile speciale ale lui (3) sunt probleme de programare liniară), se aplică de obicei următoarele perturbații standard, în funcție de parametrii y=(y 1 ,…, y m), m, Teoreme de dualitate pentru clasele generale de probleme de programare convexă afirmă că în anumite ipoteze asupra perturbației F, valorile problemelor (2) și (2*) coincid și, mai mult, soluția uneia dintre probleme este multiplicatorul Lagrange pentru cealaltă.
Când cercetăm fenomene economice metode matematice o astfel de proprietate a multor mulțimi și funcții precum convexitatea se dovedește a fi foarte semnificativă. Natura comportamentului multor obiecte economice se datorează faptului că anumite dependențe care descriu aceste obiecte sunt convexe.
Existența sau unicitatea unei soluții este adesea asociată cu convexitatea funcțiilor și a mulțimilor sarcini economice: mulți algoritmi de calcul se bazează pe aceeași proprietate.
Valabilitatea multor afirmații referitoare la mulțimi și funcții convexe este destul de clară, sunt aproape evidente. În același timp, dovada lor este adesea foarte dificilă. Prin urmare, câteva fapte de bază legate de convexitate vor fi enunțate aici, fără dovezi, mizând pe persuasivitatea lor intuitivă.
Seturi convexe în plan.
Orice figură geometrică pe plan poate fi considerată ca o mulţime de puncte aparţinând acestei figuri. Unele mulțimi (de exemplu, un cerc, un dreptunghi, o bandă între linii paralele) conțin atât puncte interne, cât și puncte de limită; altele (de exemplu, un segment de linie, un cerc) constau numai din puncte de limită.
O mulțime de puncte dintr-un plan se numește convexă dacă are următoarea proprietate: segmentul care leagă oricare două puncte din această mulțime este cuprins în întregime în această mulțime.
Exemple de mulțimi convexe sunt: un triunghi, un segment, un semiplan (o parte a unui plan situată pe o parte a unei drepte), întregul plan.
O mulțime formată dintr-un singur punct și o mulțime goală care nu conține puncte, prin convenție, sunt de asemenea considerate convexe. În orice caz, în aceste seturi este imposibil să se deseneze un segment care să conecteze unele puncte ale acestor seturi și să nu aparțină în totalitate acestor seturi - este în general imposibil să se aleagă două puncte în ele. Prin urmare, includerea lor în numărul de mulțimi convexe nu va duce la o contradicție cu definiția, iar acest lucru este suficient pentru raționamentul matematic.
Intersecția, adică o parte comună două mulțimi convexe sunt întotdeauna convexe: luând oricare două puncte de intersecție (și sunt comune, adică aparțin fiecăreia dintre mulțimile care se intersectează) și conectându-le cu un segment, putem observa cu ușurință că toate punctele segmentului sunt comune. la ambele seturi, deci cum fiecare dintre ele este convex. Intersecția oricărui număr de mulțimi convexe va fi de asemenea convexă.
O proprietate importantă a mulțimilor convexe este separabilitatea lor: dacă două mulțimi convexe nu au comun punctele interne, atunci planul poate fi tăiat de-a lungul unei linii drepte în așa fel încât unul dintre mulțimi să se afle în întregime într-un semiplan, iar celălalt în celălalt (punctele ambelor seturi pot fi situate pe linia de tăiere). Linia dreaptă care le separă în unele cazuri se dovedește a fi singura posibilă, în altele nu este.
Punctul limită al oricărei mulțimi convexe în sine poate fi considerat ca o mulțime convexă care nu are puncte interioare comune cu mulțimea originală, prin urmare, poate fi separat de aceasta printr-o linie dreaptă. Linia care separă punctul său de limită de o mulțime convexă se numește linia de sprijin a acestei mulțimi în punctul dat. Liniile de referință în unele puncte ale conturului pot fi unice, în altele - nu unice.
Să introducem un sistem de coordonate carteziene x, y pe plan. Acum avem ocazia să considerăm diferite figuri ca mulțimi de astfel de puncte ale căror coordonate satisfac anumite ecuații sau inegalități (dacă coordonatele unui punct îndeplinesc vreo condiție, vom spune pentru scurt timp că punctul însuși satisface această condiție).
O mulțime AÌE se numește convexă dacă, împreună cu oricare două puncte x 1 și x 2, conține un segment care le leagă, adică. seturi de formă
[X 1 X 2 ]={XОE n | X=l X 1+(1-l) X 2 , 0 £l £1).
Semi-spațiile considerate mai sus sunt mulțimi convexe. Să verificăm, de exemplu, dacă semi-spațiul H + ab ( XОE n |
Să adunăm aceste două inegalități, înmulțind preliminar pe prima cu un număr arbitrar lО, iar pe a doua cu 1-l. Ca rezultat, obținem inegalitatea
l
Deoarece l este arbitrar, întregul segment care leagă punctele alese aparține semi-spațiului dat. Prin urmare, semi-spațiul este într-adevăr o mulțime convexă.
Fig. 2.10 multimi convexe (a), neconvexe (b).
Capitolul 3 Noțiuni de bază ale funcției.
3.1 Conceptul de funcții.
Fie X și Y două mulțimi. Dacă se specifică o regulă conform căreia fiecare element al mulțimii X este asociat cu un anumit element al mulțimii Y, atunci se spune că funcția este dată f, mapând X la Y. Acest fapt este scris ca f: X®Y sau y=f(x), unde x ОX, yОY. Setul X se numește zona de date sau zona de definire a funcției, iar setul Y este setul de valori. Funcţie f(x) este o regulă care permite ca fiecare valoare a lui x să fie asociată sens unic y=f(x). În acest caz, x este variabila independentă și y este variabila dependentă. Funcții y=f(x)=f(x 1 +x 2 ,..,x n), adică. sunt numite funcții cu domeniul X Ì E n și setul de valori Y Ì E funcții numerice spre deosebire de funcțiile vectoriale, pentru care YÌ E m , m>1.
O mulțime de fel
((x,y)нE n +1 ½ y=f(x) pentru unele xнX)
numit graficul unei funcții y=f(x).
Rând procese fizice poate fi descris cu funcții continue, adică funcții care au proprietatea continuității în fiecare punct x aparținând domeniilor lor de definiție.
O funcție f se numește continuă într-un punct x 0 нX dacă pentru orice număr e>0 se poate specifica un număr d e >0 astfel încât pentru toate xнX Ç Ède 1x 0 1 inegalitatea ½f(x)-f(x 0)1 Ca exemple de funcții continue pe E n , prezentăm funcția liniară f 1 (x)= unde Q este o matrice numerică simetrică de dimensiunea n * m, c este un vector din E n și b este un număr, iar Qx înseamnă produsul unei matrice cu un vector conform regulilor de înmulțire a matricei adoptate în algebra liniară. 3.2 Clasificarea funcțiilor. 3.2.1 Funcții discontinue și discrete. funcții discontinue. De exemplu, costul raportării unei cantități către un anumit sistem căldură la diferite temperaturi ale sistemului, obținem o curbă continuă pe bucăți (Fig. 3.1). există cazuri când variabila ia valori discrete (Figura 3.2). În funcție de faptul că funcția studiată este continuă sau discontinuă, ar trebui utilizate diferite metode de cercetare. Trebuie remarcat faptul că o metodă care este eficientă în analiza funcțiilor continue se poate dovedi a fi ineficientă în studiul funcțiilor discontinue, deși contrariul nu este exclus. Funcțiile pot fi clasificate și după forma lor, ceea ce determină proprietățile topologice ale funcțiilor în intervalul luat în considerare. 3.2.2 Funcții monotone. Funcția f(x) este monotonă (Figura 3.3) atât cu creștere cât și cu descreștere) dacă pentru două puncte arbitrare x 1 și x 2 astfel încât x 1 Fig.3.3. Despre conceptul de funcție monotonă. Figura 3.4 prezintă un grafic al unei funcții care scade monoton la x£0 și crește monoton la x30. Funcția își atinge minimul în punctul x=x * (origine 0) și este monotonă pe ambele părți ale punctului minim. Astfel de funcții sunt numite unimodale. Rețineți că funcția unimodală nu trebuie să fie deloc netedă (Fig. 3.4, a) și chiar continuă (Fig. 3.4, b), ea poate fi ruptă (nediferențiabilă), discontinuă (Fig. 3.4, c), discret (Fig. 3.4 d) și chiar poate să nu fie definit în unele intervale (Fig. 3.4, e.). Deci, o funcție f(x) se numește unimodală pe segment dacă este continuă și există numere a și b a£a£b£b astfel încât: 1) dacă a 2) dacă b
3) pentru xн f(x)=f * =min f(x); Fig.3.4.Funcții unimodale: a) netede, b) continue, c) discontinue, d) discrete, e) arbitrare. este posibil să se degenereze până la un punct unul sau două dintre segmentele , , (Figura 3.5). Fig.3.5. Variante de aranjare și degenerare până la un punct de segmente de monotonitate și constanță a unei funcții unimodale. setul de funcții care sunt unimodale pe un segment va fi notat cu Q. Unimodalitatea funcțiilor este o proprietate excepțional de importantă care este utilizată pe scară largă în studiile de optimizare. 3.2.3 Funcții convexe, pseudo-convexe și cvasi-convexe. Funcțiile convexe și generalizările lor (funcții pseudo-convexe și cvasi-convexe) joacă un rol important în teoria optimizării. Aceste funcții vor fi utilizate pentru a formula condiții suficiente de optimitate. O funcție numerică f definită pe o mulțime convexă X, XÌE n se numește convexă dacă pentru oricare două puncte x 1 ,x 2 нX și un număr arbitrar lн inegalitatea f(lx 1 +(1-l)x 2) £lf(x 1)+(1-l)f(x 2). (3.1) Inegalitatea sensului opus definește o funcție concavă, iar termenii „convex în jos (1)” „convex în sus (2)” sunt adesea folosiți (Figura 3.6). Fig.3.6. 1) Funcția convexă (convexă în jos), 2) Funcția concavă (concavă în sus). Geometric, convexitatea funcției f înseamnă că orice punct al unei coarde arbitrare a graficului f este situat nu mai jos decât punctul corespunzător al graficului însuși (se află sub coarda care leagă două puncte ale graficului său) (Figura 3.6. , Curba 1). Cele mai simple exemple de funcții convexe ale unei variabile sunt parabola y=x 2 și exponentul y=e x . Funcțiile y=-x 2 și y=-e x sunt concave. Dacă pentru toate x 1, x 2 ОX x 1 ¹x 2 și lО inegalitatea (3.1) este valabilă ca fiind strictă (<), то f называется strict convex
pe X (Figura 3.7, a). Funcția este numită (strict) curbat
, dacă - f este (strict) convex (Fig. 3.7, b). Fig.3.7. Funcții strict convexe (a) și strict concave, derivatele lor (linie punctată) și o funcție care are o secțiune liniară Funcţie f(x), definit pe o mulțime convexă X, se numește puternic convex cu constantă l> 0 dacă Să dăm o interpretare geometrică a definiției (3.2) luând în considerare funcția y=f(x) o variabilă. Fixare X 1 și X 2 din domeniul funcției și notând , vom schimba l de la 0 la 1. Este clar că atunci valoarea x(l), se va schimba de la x 1 inainte de x 2, și punctul ( X, f(x)) va trece prin graficul funcției y=f(x) din punctul B= ( x2, f(x2)) până la punctul în care DAR= (x 1 , f(x 1))(fig.3.8). Fig.3.8. Graficul unei funcții puternic convexe. Ecuații în planul xOy descrie o linie dreaptă L(secante) care leagă punctele DARși LA, și ecuațiile pune o parabolă R drăguț · Teorema 3.1
Funcție diferențiabilă continuu pe o mulțime convexă X f este convex pe acest set dacă și numai dacă pentru oricare x 1 ,x 2 О X adevărata inegalitate f(x 2) ³ f(x 1) +<Ñf(x 1 ,x 2 -x 1)>, (3.3) obtinut din descompunerea functiei f(x)într-o serie Taylor la un moment dat x 1 prin eliminarea termenilor de ordinul doi și superior al expansiunii F(x 1 +h) = f(x 1) + hf ¢(x 1) + h 2 /2*f¢¢(x 1) +..., (3.3) unde h este un număr suficient de mic, |h| Ñf(x 1) = (¶f/¶x 1 , ¶f/¶x 2 ,.., ¶f/¶x n) m, acestea. este un vector de derivate parțiale de ordinul întâi, calculate în punctul x 1 și se numește gradient al funcției f în punctul x 1 . · Teorema 3.2
Fie o funcție f diferențiabilă de două ori în mod continuu pe o mulțime convexă X care conține cel puțin un punct interior și fie m 2 f(x) hessianul său. Atunci pentru convexitatea lui f pe mulțimea X este necesar și suficient ca matricea m 2 f(x) să fie definită nenegativă pentru toate xнX, adică, la inegalitate <Ñ 2 f(x)h, h>³0 (3,4) ţinut pentru toate punctele xнX, hнE n . Aici matricea numerică Ñ 2 f(x) se numește Hessian (sau Hessian matrice). Dacă o funcție f are derivate parțiale continue de ordinul doi (de două ori diferențiabile continuu) într-un punct x 1 , atunci este de două ori diferențiabilă la x 1 și are o matrice hessiană de forma în plus, această matrice este simetrică, adică Afirmații similare sunt valabile și pentru funcțiile concave. În acest caz, în formulele (3.2) și (3.4), semnul de inegalitate ³ trebuie înlocuit cu £. Verificarea unei funcții pentru convexitate. O funcție f este convexă dacă matricea sa hessiană este definită pozitivă (>0) sau semidefinită pozitivă pentru toate valorile x 1 ,x 2 ,..,x n. Verificarea funcției pentru convexitate. O funcție f este convexă dacă matricea sa hessiană este semidefinită negativă (£0) pentru toate x 1 ,x 2 ,..,x n . O funcție strict convexă sau concavă are un singur extremum, care este minimul sau, respectiv, maximul global. O funcție care are o secțiune liniară (Figura 3.7, c) are un număr infinit de extreme egale ca mărime. Pentru a judeca unicitatea în prezența restricțiilor, se poate folosi conceptul de convexitate a unui set admisibil. O mulțime este convexă dacă orice segment al dreptei care leagă două puncte ale limitelor mulțimii se află în întregime în interiorul mulțimii. Convexitatea sau concavitatea funcției obiectiv poate fi, de asemenea, judecată după natura modificării derivatelor sale parțiale ¶f/¶x. În cazul unei funcții strict convexe, această derivată crește pe măsură ce argumentul crește (Fig. 3.7 a), iar pentru o funcție strict convexă scade (Fig. 3.7 b). Dacă există un segment liniar al funcției obiectiv, derivata indicată pe acest segment este constantă. Mulțimea convexă a formei X=(xнE n) | Ax£b)=(xнE n | £b i , i=1,..,m) unde A este o matrice m*n cu rânduri a 1 ,..,a m , b=(b 1 ,..,b m) н E n (m=1,2,..). Se obișnuiește să se numească poliedre sau pur și simplu poliedre. Astfel, un poliedru este o mulțime de soluții ale unui sistem cu un număr finit de inegalități liniare sau, ceea ce este același, o intersecție a unui număr finit de semi-spații (Figura 3.9). Fig.3.9. Mulțime poliedrică (poliedru). De exemplu, poligonul din fig. 2.1, a este convex, iar poligonul din fig. 2.1, b nu este convex (este situat pe ambele părți ale dreptei BC). Proprietatea generală definitorie care distinge un poligon convex de unul neconvex este că, dacă luați oricare dintre punctele sale și le conectați cu un segment, atunci întregul segment va aparține acestui poligon. Această proprietate poate fi luată ca definiție a unui set convex de puncte. Un set de puncte se numește convex dacă, împreună cu oricare dintre punctele sale, conține întregul segment care leagă aceste puncte. Conform acestei definiții, poligonul din fig. 2.1, a este o mulțime convexă, iar poligonul din fig. 2.1, b nu este astfel, deoarece segmentul WE dintre cele două puncte ale sale M și / V nu aparține complet acestui poligon. Fie M și N oricare două puncte de intersecție a două mulțimi A și B (Fig. 2.3). Deoarece punctele M și N aparțin intersecției mulțimilor, i.e. atât o mulțime convexă A cât și o mulțime convexă B, apoi conform definiției unei mulțimi convexe, toate punctele segmentului MI vor aparține atât mulțimii A cât și mulțimii B, adică. intersectia acestor multimi. Și asta înseamnă că intersecția acestor mulțimi este o mulțime convexă. ■ Printre punctele unei mulțimi convexe, se pot evidenția punctele interioare, de limită și de colț. Un punct al unei mulțimi se numește intern dacă o parte din vecinătatea sa conține puncte doar din această mulțime. Fig- 2-3 Punctul mulțimii se numește graniță, dacă vreuna din vecinătățile sale conține atât puncte care aparțin mulțimii date, cât și puncte care nu îi aparțin. Punctele de colț sunt de interes deosebit în problemele de programare liniară. Un punct al unei mulțimi se numește punct de colț (sau extrem) dacă nu este intern niciunui segment care aparține în întregime mulțimii date. Pe fig. 2.4 prezintă exemple de diferite puncte ale poligonului: interior (punctul M), limită (punctul I) și colțul (punctele A, B, C, D E). Punctul A este unghiular, deoarece pentru orice segment care aparține în întregime poligonului, de exemplu, segmentul AP, acesta nu este intern; punctul A este intern segmentului Kb, dar acest segment nu aparține în întregime poligonului. Pentru o mulțime convexă, punctele de colț coincid întotdeauna cu vârfurile poligonului (poliedrul), în timp ce, în același timp, acest lucru nu este necesar pentru o mulțime neconvexă. Deci, în fig. 2,5 punctul A este un vârf al unui poligon neconvex, dar nu unul de colț (este intern segmentului Kb, care aparține în întregime acestui poligon). Un set de puncte se numește închis dacă include toate punctele sale limită. Un set de puncte se numește mărginit dacă există o bilă (cerc) de rază de lungime finită centrată în orice punct al mulțimii care conține complet mulțimea dată; în caz contrar, mulțimea se numește nemărginită. Dacă o figură este limitată doar la linii drepte sau segmentele acestora, atunci numărul punctelor sale de colț este finit; în cazul limitelor curbilinie, figura conține infinit de puncte de colț, ceea ce ne permite să facem următoarea definiție. Un set convex închis de puncte dintr-un spațiu (plan) care are un număr finit de puncte de colț se numește poliedru (poligon) convex dacă este mărginit și regiune poliedrică (poligonală) convexă dacă este nelimitat. Până acum am luat în considerare seturi convexe de puncte în plan și în spațiu. Analitic, astfel de puncte sunt reprezentate printr-o pereche ordonată de numere (xx x2) sau un triplu ordonat de numere (*1, *2, *h).Conceptul de punct poate fi generalizat, adică printr-un punct (sau un vector). ) o mulțime ordonată de n numere ., xn), în care numerele xx, x2, ..., xn sunt numite coordonatele unui punct (vector). O astfel de generalizare are sens, deoarece dacă luăm orice obiect economic, atunci două sau trei numere nu sunt de obicei suficiente pentru a-l caracteriza și este necesar să luăm n numere, unde n > 3. Mulțimea tuturor punctelor X = (xx x2,..., xn) este un spațiu de puncte n-dimensional (vector). Pentru n > 3, punctele și figurile unui spațiu n-dimensional nu au o semnificație geometrică reală, iar toate studiile obiectelor din acest spațiu trebuie efectuate într-o formă analitică. Cu toate acestea, se dovedește a fi oportun să fie utilizat în acest caz concepte geometrice pentru a facilita ideile despre obiectele „-spațiului dimensional. III. Seturi și funcții convexe 569 3.
Toate funcțiile unei variabile cu elasticitate constantă ω au forma (8) (utilizați egalitatea (4)). 4.
Funcțiile mai multor variabile cu elasticități parțiale constante sunt funcții de putere ale formei y = Ax1 B 1 x2 B 2 ,...,xN B N . III. Seturi și funcții convexe În studiul fenomenelor economice prin metode matematice, o astfel de proprietate a multor mulțimi și funcții precum convexitatea se dovedește a fi foarte semnificativă. Natura comportamentului multor obiecte economice este legată de fapt. că anumite dependențe care descriu aceste obiecte sunt convexe. Existența sau unicitatea soluționării problemelor economice este adesea asociată cu convexitatea funcțiilor și a mulțimilor: mulți algoritmi de calcul se bazează pe această proprietate. Valabilitatea multor afirmații referitoare la mulțimi și funcții convexe este destul de clară, sunt aproape evidente. În același timp, dovada lor este adesea foarte dificilă. Prin urmare, câteva fapte de bază legate de convexitate vor fi prezentate aici, fără dovezi, mizând pe persuasivitatea lor intuitivă. 1. Mulțimi convexe în plan Orice figură geometrică din plan poate fi considerată ca un set de puncte aparținând acestei figuri. Unele mulțimi (de exemplu, un cerc, un dreptunghi, o bandă între linii paralele) conțin atât puncte interne, cât și puncte de limită; altele (de exemplu, un segment, un cerc) constau numai din puncte de limită. O mulțime de puncte dintr-un plan se numește convexă dacă are următoarea proprietate: segmentul care leagă oricare două puncte din această mulțime este cuprins în întregime în această mulțime (Fig. 1). Exemple de mulțimi convexe sunt: un triunghi, un segment, un semiplan (o parte a unui plan situată pe o parte a unei drepte), întregul plan. Alte exemple de seturi convexe sunt prezentate în fig. 2a. Pe fig. 2b prezintă exemple de mulțimi neconvexe. O mulțime formată dintr-un singur punct și o mulțime goală care nu conține puncte, prin convenție, sunt de asemenea considerate convexe. În orice caz, în aceste mulțimi este imposibil să se deseneze un segment care să conecteze unele puncte ale acestor mulțimi și să nu aparțină în totalitate acestor mulțimi, - în ele 570 Aplicație matematică Orez. 1. Un segment care leagă oricare două puncte ale unei figuri convexe este cuprins în întregime în el. Orez. 2. Mulțimi convexe (a) și neconvexe (b) pe plan. nu se pot selecta deloc două puncte. Prin urmare, includerea lor între mulțimile convexe nu va duce la o contradicție cu definiția, iar acest lucru este suficient pentru raționamentul matematic. Intersecția, adică partea comună a două mulțimi convexe, este întotdeauna convexă: luând oricare două puncte de intersecție (și sunt comune, adică aparțin fiecăreia dintre mulțimile care se intersectează) și conectându-le cu un segment, putem vedea cu ușurință că toate punctele segmentului i sunt comune ambelor mulțimi, deoarece fiecare dintre ele este convexă. Tu - intersecția oricărui număr de mulțimi convexe va fi de asemenea convexă. O proprietate importantă a mulțimilor convexe este separabilitatea lor: dacă două mulțimi convexe nu au puncte interioare comune, atunci planul poate fi tăiat de-a lungul unei linii drepte în așa fel încât una dintre mulțimi să se afle în întregime într-un semiplan, iar altul în celălalt (pe linia de tăiere).pot fi localizate puncte ale ambelor seturi). Linia dreaptă care le separă în unele cazuri x se dovedește a fi singura posibilă, în altele nu este (Fig. 3). Punctul limită al oricărei mulțimi convexe în sine poate fi considerat ca o mulțime convexă care nu are cu mulțimea inițială Orez. 3. Liniile de separare. Orez. 4. Liniile de referință. III. Seturi și funcții convexe 571 prin puncte interioare comune, prin urmare, poate fi separat de acesta printr-o linie dreaptă. Linia care separă punctul său de limită de o mulțime convexă se numește linia de sprijin a acestei mulțimi în punctul dat. Liniile de referință în unele puncte ale conturului pot fi singurele, în altele nu sunt singurele (Fig. 4). Să introducem un sistem de coordonate carteziene x, y pe plan. Acum avem ocazia să considerăm diferite figuri ca mulțimi de astfel de puncte ale căror coordonate satisfac anumite ecuații sau inegalități (dacă coordonatele unui punct satisfac o anumită condiție, vom spune pentru scurt timp că punctul însuși satisface această condiție). Exercitiul 1 Se consideră figuri ale căror puncte satisfac inegalitățile: a) y ³ x2 ; b)xy³ 1; c)xy³ 1, x > 0; d) |x| + |ó|£ 2; e) (õ+1)2 + (ó – 2)2 £ 9. Care dintre ele sunt convexe? Ecuația liniară ax + by = c este satisfăcută de punctele dreptei. Cu alte cuvinte, linia dreaptă este soluția acestei ecuații. Rezolvarea inegalității liniare Soluția fiecăreia dintre inegalități este un semiplan. Soluția sistemului este un set de puncte, fiecare dintre ele satisface toate inegalitățile sistemului, adică soluția sistemului de inegalități este intersecția tuturor soluțiilor inegalităților individuale care alcătuiesc sistemul. Un semiplan este o mulțime convexă, iar intersecția mulțimilor convexe este întotdeauna convexă. Astfel, soluția sistemului (2) este o mulțime convexă. Pe fig. 5 arată soluția sistemului de inegalități ïî - 2x - y ³ -7. Orez. 5. Rezolvarea unui sistem de trei inegalități liniare. 572 Aplicație matematică Rețineți că inegalitatea ax + cu £ c poate fi înlocuită cu o inegalitate echivalentă –àõ – by³ –ñ având forma (1). În plus, ecuația ax + by = c este echivalentă cu următoarea pereche de inegalități: ( ax + cu ³ c; ax + cu £ c. Astfel, soluția unui sistem de ecuații liniare și inegalități este întotdeauna o mulțime convexă. Exercițiul 2 Va rezolvarea sistemului ai x + bi y > ci , i = l, 2, ..., N set convex? Cum diferă de soluția sistemului s (2)? Exercițiul 3 Vino cu sisteme de inegalități ale căror soluții vor fi: a) un paralelogram; b) interiorul colțului; c) o bandă între două drepte paralele; d) un singur punct; e) multimea goala. 2. Funcții convexe ale unei variabile Cel mai simplu mod de a defini o funcție convexă este geometric. Pentru aceasta, este utilă introducerea conceptului de epigrafă a unei funcții. Epigraful unei funcții este mulțimea de puncte situate deasupra graficului funcției și pe graficul însuși. Mai strict, epigraful funcției f(x) este mulțimea unor astfel de puncte a căror coordonată x se află în domeniul funcției și a căror coordonată y satisface inegalitatea y ³ f(x). O funcție se numește convexă în jos dacă epigraful ei este o mulțime convexă. Orez. 6 ilustrează această definiție. Orez. 6. Epigraful unei funcții convexe. Orez. 7. Punctul coardei nu poate fi sub grafic. III. Seturi și funcții convexe 573 Definiția de mai sus este destul de riguroasă și poate fi tradusă fără ambiguitate în limbaj analitic. În primul rând, funcția f(x) trebuie să aibă un domeniu de definiție convex - un segment, o rază sau întreaga linie. În caz contrar, epigraful s-ar sparge în mai multe zone separate, iar segmentul care leagă punctele din zone diferite ar trece prin „zona interzisă”. Pentru a afla ce condiție trebuie să îndeplinească valorile funcției convexe descendente f(x), „selectăm oricare două puncte M1 și M2 de pe graficul său și desenăm o coardă M1 M2 (Fig. 7). Trebuie să se afle în întregime în epigraf, adică orice punct M al coardei trebuie să aparțină epigrafului. Luați în considerare numărul l care arată proporția în care punctul M împarte coarda: l = M2M. M2 M1 Această valoare se află în intervalul 0 £ l £ 1. Este clar că în aceeași proporție abscisa și ordonata punctului M împart segmentele è [ó1 , ó2 ]: õ2 – õ3 =l (õ2 – x1 ); y2 – y3 =l (y2 – y1 ); õ3 =l x1 + (1 –l )õ2 ; y3 =l y1 + (1 –l )y2 . Condiția ca un punct să aparțină inegalității y3 ³ f(õ3 ). Și astfel inegalitatea poate fi reprezentată în M supragraf - așa este y 1 \u003d f (x 1), y 2 \u003d f (õ 2) - aceasta Dacă inegalitatea (3) este satisfăcută pentru orice valoare a lui x1 è õ2 , atunci orice coardă se află în epigraf și, cu atât mai mult, orice segment care leagă punctele situate mai sus se află în epigraf. Astfel, o funcție f(x) definită pe o mulțime convexă este convexă în jos dacă are următoarea proprietate: pentru orice două numere x1 × õ2 din domeniul funcției și orice număr l din interval, inegalitatea (3) este valabilă. Inegalitatea (3) este adesea scrisă într-o formă „simetrică”. 574 Aplicație matematică Orez. 8. Funcții: convex în jos (a), convex în sus (b), neavând semn permanent umflături (c). Funcțiile care sunt convexe în sus pot fi definite în mod similar: pentru aceasta, semnele de inegalitate (3) și (4) trebuie înlocuite cu unele opuse. Funcțiile care sunt convexe în jos sunt adesea denumite simplu „convexe”. Funcțiile convexe au o proprietate mai generală decât inegalitatea (4). Dacă x1 , õ2 ,..., xN sunt valori arbitrare ale argumentului l 1 ,l 2 ,..., lN - numere nenegative, a cărui sumă este egală cu unu, atunci Alegem patru valori ale argumentului x1< õ2
< õ3
< õ4
è ïðî- trageți o coardă M1 M4 (Fig. 9). Punctele intermediare M2 și Ì3 se află în epigraf, astfel încât unghiul înclinarea acordului M M * nu mai mult, și acordurile M * M Nu mai puțin decât M M* unghiul coardei abscisă (unghiuri de înclinare – luând în considerare semne!). Prin urmare, viteză creșterea funcției convexe în zone de valori „mari” ale ar- gumenta (în zona [х3, х4]) nu mai puțin decât în zona „mică” valori (). A se intoarce catre în x 2® x 1è ® x 3, f¢(x3) ³f¢(x1 ), Orez. 9. Acord trasat în zonă derivat ¢(x) diferențiere funcția convexă f (x) - nu - valori mari argument, are III. Seturi și funcții convexe 575 Dacă derivata f¢(x) este diferențiabilă (adică funcția convexă f(x) este de două ori diferențiabilă), atunci f¢¢(x) ³ 0. Pentru funcțiile de două ori diferențiabile, această inegalitate se dovedește a fi echivalentă cu definiția de mai sus a unei funcții convexe; în cursuri analiză matematică convexitatea este determinată de obicei de semnul derivatei a doua. Dar în aplicațiile economice, unde deseori trebuie să se ocupe de funcții ale căror grafice au pauze, o astfel de definiție este de puțin folos. Dacă f(x) și g(x) sunt funcții convexe și a ³ 0, atunci funcțiile a) f(x) + g(x); c) max(f(x), g(x)). Convexitatea funcțiilor din a) și b) se verifică direct folosind inegalitatea (3) sau (4). Funcția c) pentru fiecare x ia o valoare egală cu cea mai mare dintre valorile lui f(x) și g(x) (și oricare dintre ele dacă sunt egale). Epigraful funcției max(f(x), g(x)) este intersecția epigrafelor funcțiilor f(x) și g(x) (verificați!) - de unde convexitatea funcției c). Exercițiul 4 Există funcții convexe în jos și convexe în sus în același timp? Exercițiul 5 Cum arată graficul funcției f(x) = max (0, a + bx) pentru diferite valori ale parametrilor a și b? Sunt aceste funcții convexe? Exercițiul 6 Funcția este convexă Orez. 10. Grafice ale funcțiilor f(x) (1), g(x) N (2) и max(f(x), g(x)) (3). f(x) = å fi (x) , fi(x) = max(0, ai + bi x)? Cum arată programul ei? 576 Aplicație matematică Un exercitiu Considera ax, f(x) = i ïï
B × (x - 1) , x ³ 1. Pentru ce valori ale lui a și b această funcție Curbat în jos? Curbat în sus? -
nu are un semn convex permanent? IV. Spațiul binecuvântărilor Noțiuni de bază Mulți întrebări teoretice sunt discutate în manualul nostru pentru cazul a două produse. Ca instrument convenabil care simplifică semnificativ analiza acestora, s-au folosit construcții grafice, în care o mulțime care include două produse în cantități x1, è x2 a fost reprezentată printr-un punct pe un plan cu coordonate carteziene(x1, x2). Traducere concepte teoreticeîn limbaj geometric a făcut ca proprietățile fenomenelor în discuție să fie foarte clare și, în același timp, nu a dus la o pierdere de rigoare: toate conceptele geometrice (linii drepte, curbe, unghiuri de înclinare etc.) aveau echivalente analitice precis definite - ecuații , derivate, relații între parametri etc. Prin urmare, astfel de construcții sunt utilizate pe scară largă atât în manualele de economie, cât și în publicațiile științifice. Cu toate acestea, aceste raționamente geometrice au fost riguroase și precise doar pentru cazurile în care lista bunurilor de consum includea doar două articole. În realitate, numărul de beneficii pe care le folosesc oamenii este mult mai mare. Concluziile la care se ajunge geometric pot fi considerate ca având suficientă generalitate dacă pot fi extinse la cazurile unui număr arbitrar de bunuri.
În aplicațiile de inginerie, nu este neobișnuit să fie utilizat
f(x 1)³ (x 2) (funcție descrescătoare monotonă)
, care trece prin puncte DARși LA. Inegalitatea (3.2) în acest caz înseamnă că graficul funcției y = f(x) pe planul xOy se află sub nu numai secanta care leagă punctele DARși LA, dar și a parabolei Р a cărei deformare este determinată de parametru lși poate fi ales arbitrar mic. Cu alte cuvinte, în zona delimitată de secanta și graficul funcției, puteți construi o parabolă care conectează punctele DARși LA.
