1.
2. instructiuni de utilizare mat. modele în economie.
Modelele matematice fac posibilă determinarea valorilor optime ale parametrilor necunoscuți ai sistemelor economice, ceea ce este important în procesul decizional. Programarea matematică oferă doar un aparat care vă permite să optimizați procesul de selecție cele mai bune opțiuni planuri în procesul de management în sistemele economice.
Folosit în statistica matematică, metode de optimizare, metode economice. cibernetică, probleme experimentale.
La studierea proceselor și fenomenelor complexe din economie, se folosește foarte des modelarea - o afișare concretă bine definită a caracteristicilor considerate ale obiectului studiat. Esența sa constă în faptul că fenomenul studiat este reprodus în condiții experimentale folosind un model la o scară temporală și spațială diferită. Un model este un obiect special creat cu ajutorul căruia sunt reproduse anumite caracteristici ale sistemului studiat pentru a-l studia. Modelarea matematică este cea mai perfectă și în același timp eficientă metodă de obținere a informațiilor despre obiectul studiat. Este un instrument puternic de analiză în economie. Rezultatele cercetării utilizând modele vor fi de interes practic atunci când modelul construit este suficient de adecvat fenomenului luat în considerare, i.e. suficient de bine pentru a reflecta situația reală.
2. programarea matematică ca știință, structura ei. Probleme de optimizare. Dificultăţi în aplicarea metodelor clasice de optimizare în rezolvarea problemelor economice.
Programare matematică este o ramură a matematicii aplicate care se dezvoltă baza teoreticași metode de rezolvare a problemelor extreme.
Programarea matematică include o serie de secțiuni, dintre care principalele sunt următoarele:
1. Programare liniară. Această secțiune include probleme în care variabile necunoscute sunt incluse în relații matematice de gradul I.
2. Programare neliniară. Această secțiune include probleme în care funcția obiectiv și (sau) constrângerile pot fi neliniare.
3. Programare dinamică. Această secțiune include sarcini în care procesul de soluție poate fi împărțit în etape separate.
4. Programare cu numere întregi. Această secțiune include sarcini în care variabilele necunoscute pot lua numai valori întregi.
5. Programare stocastică. Această secțiune include sarcini care conțin variabile aleatoareîn funcţia obiectivă sau constrângeri.
6. Programare parametrica. Această secțiune include probleme în care coeficienții variabilelor necunoscute din funcția obiectiv sau constrângeri depind de unii parametri.
Pentru a rezolva problemele de programare matematică, este dificil să se utilizeze metode clasice pentru găsirea unui extremum, deoarece în problemele de programare matematică funcția obiectiv atinge valoarea sa extremă la limita regiunii valorilor acceptabile ale variabilelor necunoscute, iar derivatele nu există. la punctele de limita. O enumerare completă a punctelor admisibile este imposibilă din cauza numărului lor semnificativ.
3. Conceptul de model matematic, tipuri de mat. modele
Model matematic este o abstractizare a unui fenomen sau proces real scrisă în simboluri și expresii matematice. Modelele matematice ale proceselor și fenomenelor economice sunt numite modele economice și matematice
Modelele sunt împărțite în:
1. liniar, în care toate dependențele sunt descrise prin relații liniare,
2. neliniară, în care există relații neliniare;
3. stocastică, care țin cont de natura aleatorie a proceselor studiate,
4. determinat, care iau în considerare valorile medii ale tuturor parametrilor.
5. dinamic modele în care sistemele studiate sunt considerate în dezvoltare pe mai multe perioade,
6. static, în care factorul timp nu este luat în considerare.
7. optimizare modele in care alegerea se face in functie de extremizarea un anumit criteriu,
8. neoptimizare, în care nu există un criteriu de optimitate.
9. macromodele(pentru întreaga gospodărie)
10. micromodele(legături sau procese individuale ale economiei).
Tipuri de modele matematice: liniare, neliniare, pătratice, întregi, discrete, parametrice, liniare fracționale, dinamice, stocastice
4. Expunere generală a problemelor de programare matematică.
Luați în considerare enunțul general al problemei programării matematice.
Problema generală a programării matematice este de a determina valoarea optimă a funcției obiectiv, iar valorile variabilelor trebuie să aparțină unui anumit interval de valori admisibile. Definiție matematică soluție optimă exprimat în găsirea extremului (max sau min) al unei funcții de mai multe variabile
Z = f(x1, x2, …, xn)
în intervalul dat de modificare a acestor variabile
gi (x1, x2,…, xn)Ribi (i = 1, 2,…, m),
unde Ri este unul dintre semnele ≥, =, ≤.
5. Problema optimizarii planului de productie. Formularea economică și construcția unui model matematic de probleme.
Cadrul economic:
Firma produce n tipuri de produse care folosesc m tipuri de materii prime. Pentru producerea unei unități de producție se utilizează o cantitate strict definită de materii prime de un fel sau altul. Materiile prime de fiecare tip în întreprindere sunt limitate. Firma primește un anumit profit din vânzarea unei unități de producție. Este necesar să se găsească un astfel de plan de producție în care întreprinderea să primească profitul total maxim.
Setare matematică:
Fie j indicele tipului de produs j = 1, n
i - indicele tipului de resursă i = 1, m
iar ij sunt costurile materiilor prime i-al-lea tip pentru producerea unei unităţi de producţie j-al-lea tip;
Аi este o limită dată a volumului disponibil de resurse de tipul i;
Pj - profitul primit din vânzarea unei unități de producție de tip j-a;
xj este volumul de ieșire de tipul j-lea.
z \u003d P1x 1 + P2x 2 + ... + Pnx n → max
a11x 1 + a12x 2 +…+ a1nx n ≤ A1
a21x 1 + a22x 2 +…+ a2nx n ≤ A2
…………………………….
a m1x1 + a m2x2 +…+ a m n x n ≤ Am
xj ≥ 0, j = 1, n
6. Sarcina dietei. Formularea economică și construirea unui model matematic al problemei.
Cadrul economic
Unele ferme hrănesc animale. Folosit pentru îngrășare n tipuri de furaje. Conținutul de nutrienți (calciu, fosfor etc.) este cunoscut pe unitatea de hrană a fiecărei specii. Pentru o alimentație adecvată a animalelor, este necesar să se consume nutrienți nu mai puțin decât cantitățile specificate. Costul unitar al fiecărei furaje este cunoscut. Este necesar să se determine dieta de hrănire a animalelor, în care costul total al îngrășării va fi minim.
Setare matematică:
j este indicele tipului de alimentare, j = 1, n
i – indicele tipului de nutrient, i = 1, m
Аi este aportul zilnic necesar al i-lea tip de nutrient;
Сj este costul unei unități de furaj de tip j-lea.
Să introducem variabile necunoscute:
хj - volumul zilnic de hrănire a animalelor j-a vedere rautacios.
În ceea ce privește notația introdusă sarcina dată va fi scris în continuare
a11x1 + a12x2 +…+ a1nxn ≥ A1
a21x1 + a22x2 +…+ a2nxn ≥ A2
…………………………….
am1x1 + am2x2 +…+ și mnxn ≥Am
xj ≥ 0, j = 1, n
7. Sarcina de transport . Formularea economică și construirea unui model matematic al problemei.
Cadrul economic :
Disponibil m furnizori de produse omogene şi n consumatorii acestui produs. Costuri unitare cunoscute pentru livrarea unei unități de producție de la fiecare furnizor către fiecare consumator. Stocurile furnizorilor sunt limitate. Sunt cunoscute și nevoile de produse ale fiecărui consumator.
Este necesar să se determine un astfel de plan pentru transportul produselor de la furnizori la consumatori, în care costul total al transportului să fie minim.
Setare matematică :
Să introducem denumirile parametrilor dați:
j – indicele de consum, j = 1, n
i – indicele furnizorului, i = 1, m
Аi este volumul de produse disponibile de la al-lea furnizor;
Bj - volumul cererii pentru produsele consumatorului j;
Cij este costul unitar al transportului unei unități de produs de la al-lea furnizor la al-lea consumator.
Să introducem variabile necunoscute:
хij este volumul de transport al produselor de la al-lea furnizor la al-lea consumator.
z = С11x11 + С12x12 +…+С1nx1n + С21x21 +…+ Сm(n -1)xm (n-1) + Сmnxmn → min
Restricții de sarcină.
I. De la fiecare furnizor, puteți retrage produse nu mai mult decât cantitatea disponibilă:
x11 + x12 +…+ x1n ≤ A1
x21 + x22 +…+ x2n ≤ A2 (2)
…………………….
xm1 + xm2 +…+ xmn ≤ Am
II. Nevoia de produse a fiecărui consumator trebuie satisfăcută
x11 + x21 +…+ xm1 ≥B1
x12 + x22 +…+ xm2 ≥B2
……………………. (3)
x1n + x2n +…+ xmn ≥Bn
III. Condiție de non-negativitate: xij ≥0, i = 1, m ; j = 1, n
Este adesea convenabil să scrieți declarația matematică într-o formă pliată:
, i = 1, m 
, j = 1, n
8. Problema alegerii sarcinilor sau a sarcinilor. Formularea economică și construirea unui model matematic al problemei.
Cadrul economic :
Disponibil n tipuri de muncă şi n interpreți. Fiecare dintre interpreți poate îndeplini orice, dar numai o singură lucrare. Costul efectuării fiecărei lucrări de către fiecare interpret este stabilit. Este necesar să se atribuie executanților să lucreze astfel încât costul total al finalizării lucrării să fie minim.
Setare matematică .
Să introducem notația pentru parametrii dați.
i – indicele lucrărilor, i = 1, m
j este indicele performanților, j = 1, n
Cij este costul efectuării celui de-al i-lea loc de muncă de către al-lea executant.
Să introducem variabile necunoscute. În această problemă, variabilele necunoscute pot lua doar două valori, 0 sau 1. Astfel de variabile sunt numite variabile nule.
1 - în cazul în care executantul j este repartizat la locul de muncă i;
0 - altfel.
În ceea ce privește notația introdusă, această problemă poate fi scrisă astfel:
z = С11x11 + С12x12 +…+С1nx1n + С21x21 …+ С(n-1)(n-1)x(n-1)(n-1) + Сnnxnn → min
I grup de restricții.
Pentru fiecare lucrare ar trebui să i se aloce un singur interpret:
x11 + x12 +…+ x1n = 1
x21 + x22 +…+ x2n = 1
……………………..
xn1 + xn2 +…+ xnn = 1
II. grup de restricție.
Fiecare executor poate executa o singură lucrare:
x11 + x21 +…+ xn1 = 1
x12 + x22 +…+ xn2 = 1
……………………..
x1n + x2n +…+ xnn = 1
x ij = ( 0,1) i = 1, n ; j = 1, n
9. Problema tăierii materialelor. Formularea economică și construirea unui model matematic al problemei.
Cadrul economic .
Materia prima de aceeasi dimensiune este furnizata pentru taiere. Este necesar să-l tăiați în semifabricate de o dimensiune dată într-o anumită cantitate, astfel încât deșeurile totale să fie minime.
Setare matematică .
Să introducem notația:
i este indicele spațiilor libere,
Аi - numărul necesar de spații libere de tipul i;
j - indicele opțiunilor de tăiere,
Cj este dimensiunea deșeurilor la tăierea unei unități de material inițial conform opțiunii j;
și ij este numărul de semifabricate de tip i-lea la tăierea unei unități de material inițial conform opțiunii j.
Să introducem notația variabilelor necunoscute.
xj este cantitatea de materie primă tăiată conform opțiunii j.
În ceea ce privește notația introdusă, această problemă poate fi scrisă astfel:
z \u003d С1x1 + С2x2 + ... + Сnxn → min
a11x1 + a12x2 +…+ a1nxn = A1
a21x1 + a22x2 +…+ a2nxn = A2
…………………………….
am1x1 + am2x2 +…+ amnxn =Am
xj ≥ 0, j = 1, n
Utilizarea modelelor matematice vă permite să economisiți până la 20% din materii prime.
Modelul matematic de tăiere este construit în două etape.
În prima etapă, se construiesc opțiunile de tăiere, în urma cărora valorile numărului de opțiuni n, numărul de semifabricate de fiecare tip obținut prin diverse opțiuni tăiere (aij), precum și valoarea deșeurilor (Cj).
Construcția opțiunilor pentru tăierea unei unități de material sursă se realizează sub forma următorului tabel:
| numărul opțiunii |
Gol i1 |
i2 gol |
gol im |
Spaturile sunt aranjate în ordinea necrescătoare a dimensiunilor lor. Construirea variantelor se realizează prin metoda enumerarii complete.
10. Forma generală a modelului problemei LP și caracteristicile acestuia
Forma generală a LLP este:
z \u003d С1x1 + ... + Сnxn max (min)
a11 X1 + a12 X2 + … + a1n Xn R1 a1
a21 X1 + a22 X2 + … + a2n Xn R2 a2
………………………………………………….
am1 X1 + am2 X2 +…+ amnxn Rm am
xj ≥ 0, j = 1, k, k ≤ n
În formă generală, fiecare simbol R1 , R2 ,…, Rm înseamnă unul dintre semnele: ≥, = sau ≤ .
Forma generală a modelului problemei LP are următoarele caracteristici.
1. Sistemul de constrângeri este prezentat sub formă de ecuații (condiții rigide) și inegalități (condiții nerigide).
2. Condițiile de non-negativitate nu sunt impuse tuturor variabilelor
3. Funcția obiectiv tinde fie la maxim, fie la minim.
11. Forma standard a modelului problemei LP și caracteristicile acestuia
Forma standard este după cum urmează.
Aflați maximul sau minimul funcției obiectiv z:
z = С1x1 + … + Сnxn → max (min) (1)
Sub rezerva următoarelor restricții:
a11 X1 + a12 X2 + … + a1n Xn ≤ a1
a21 X1 + a22 X2 + ... + a2n Xn ≤ a2
…………………………………………..
am1 X1 + am2 X2 +… + amn Xn ≥ am
xj ≥ 0, j = 1, k, k ≤ n
Caracteristicile formei standard a modelului problemei LP sunt următoarele:
1. sistemul de restricții se prezintă sub formă de inegalități (condiții nerigide)
2. tuturor variabilelor se impun condiţii de non-negativitate
3. funcția obiectiv tinde fie la max, fie la min
12. Forma canonică a modelului problemei LP și caracteristicile acestuia
Forma canonică este:
Aflați minimul funcției obiectiv z:
z = С1x1 + … + Сnxn → min
Sub rezerva următoarelor restricții:
a11 X1 + a12 X2 + ... + a1n Xn = a1
a21 X1 + a22 X2 + ... + a2nxn = a2
…………………………
am1x1 + am2 X2 +… + amn Xn = am
Xj ≥0, j = 1, n
Caracteristicile formei canonice sunt următoarele:
1. Sistemul de restricții este prezentat sub formă de ecuații (condiții stringente).
2. Condițiile de non-negativitate se aplică tuturor variabilelor
3. Funcţia obiectiv tinde să
În unele surse, funcția obiectivă a problemei LP, prezentată sub formă canonică, tinde spre maxim. Acest lucru se face pentru comoditatea rezolvării problemei conform algoritmului dezvoltat pentru funcția obiectiv maxim.
13. Plan de sarcini de bază posibil, admisibil, optim, ODZ al sarcinii LP
Definiția 1. Valori ale variabilelor necunoscute care satisfac toate constrângerile problemei programare liniară, sunt numite admisibilă valori variabile sau planuri .
Definiția 2. Setul tuturor planurilor pentru o problemă de programare liniară se numește domeniul valorilor admisibile ale variabilelor ( ODZ ).
Definiția 3. Planul problemei de programare liniară, în care funcția obiectiv ia valoarea minimă (sau maximă) pe ODZ se numește optim .
14. Tipuri de înregistrări ale sarcinilor LP: extins, pliat, matrice, vector.
Modelele de probleme LP pot fi scrise sub diferite forme.
1. Vedere extinsă a înregistrării modelului
Z = c1 X1 + c2 X2 + … + cn Xn → min
a11 X1 + a12 X2 + … + a1n Xn = a1,
a21 X1 + a22 X2 + … + a2n Xn = a2,
……………………………………………
a m1 X1 + am2 X2 + … + amn Xn = am,
Xj ≥ 0, j = 1, n.
2. Vizualizare restrânsă:
,
Xj ≥ 0, j = 1, n.
3. Modelul problemei LP sub formă de matrice:
X ≥ 0
Unde 
a11 a12 … a1n X1 a1
A= a21 a22 … a2n , X= X2 , A0 = a2
… … … … … …
am1 am2 … amn X3 am
4. Modelul problemei LP în formă vectorială:
Unde
X1 a11 a12 a1n a1
X2 , a21 , a22 , a2n , a2
… … … … …
Хn am1 am2 am2 am
15. Trecerea de la forma standard și generală a problemelor LP la cea canonică. Teorema conexiunii
Pentru a trece de la o formă generală sau standard la una canonică, se folosesc următoarele tehnici.
1. Conversie variabilă. Dacă o variabilă Xk este nepozitivă (Xk ≤ 0), atunci se introduce o nouă variabilă Xk ", astfel încât Xk " = –Xk . Evident, Xk " ≥ 0. După aceea, în fiecare constrângere și funcție obiectiv, variabila Xk este înlocuită cu [ – Xk "].
Dacă o variabilă Xt poate lua orice valoare, atunci ea este înlocuită cu diferența dintre două variabile nenegative Xt' și Xt'', adică se presupune că xt = Xt' – Xt'', unde Xt' 0 ≥ și Xt'' ≥ 0.
2. Transformarea constrângerii. Dacă oricare dintre constrângerile din model are forma unei inegalități, atunci este convertită în egalitate prin adăugarea (dacă inegalitatea este de tip ≤) sau scădere (dacă inegalitatea este de tip ≥) din partea stângă. Aceste variabile se numesc variabile de echilibru. Variabilele de echilibru sunt incluse în funcția obiectiv cu coeficienți zero. Variabila de sold ia valoarea indicelui succesiv după cele deja existente. Dacă, de exemplu, sistemul de restricții are 5 variabile, atunci prima variabilă de echilibru va fi X6, iar a doua - X7 etc.
16. Trecerea de la forma canonică a modelului ZLP la standard
Pentru a trece de la forma canonică la forma standard, fiecare dintre
ecuațiile care trebuie înlocuite cu un sistem de inegalități:
O altă modalitate este de a aduce sistemul de ecuații într-o formă specială și de a elimina în continuare unele variabile.
Folosind metoda Jordan-Gauss, selectăm variabila de bază din fiecare ecuație. O astfel de selecție se realizează cu ajutorul transformărilor gaussiene echivalente (elementare). Acestea includ:
a) înmulțirea oricărei ecuații cu o constantă diferită de zero;
b) adăugare la orice ecuație a oricărei alte ecuații, înmulțită cu orice constantă.
Este convenabil să scrieți sistemul inițial de ecuații liniare înainte de transformare sub forma unei matrice sau a unui tabel:
Scriem problema în formă standard.
17. Conceptul de hiperplan al unui semiplan, un hiperplan de sprijin.
18. Geometric. interpretarea sistemului de constrângeri și a funcției obiectiv în problemele LP
19. Mulțimea convexă: punctele extreme (de colț) ale mulțimii. Poliedru convex
Definiție O mulțime M se numește convexă dacă, împreună cu oricare două puncte aparținând mulțimii date, conține și un segment care le leagă.
 |
mulţime convexă
Definiție Un punct x al unei mulțimi M se numește colț sau punct extrem dacă nu este intern niciunui segment care aparține în întregime mulțimii date.
Teorema 1. Orice punct al unui segment poate fi reprezentat ca o combinație convexă a punctelor sale de colț.
x \u003d λ 1 A + λ 2 B
λ 1 , λ 2 ≥ 0 combinație convexă a punctelor punctelor de colț A și B
λ1 + λ2 = 1
Teorema 2. Orice punct al unei mulțimi închise convexe poate fi reprezentat ca o combinație convexă a punctelor sale de colț.
20. Algoritmul metodei grafice de rezolvare a problemelor LP
1. Se verifică dacă LPP-ul original este în forma standard, dacă nu, atunci sarcina trebuie convertită în formularul standard.
2. Se verifică numărul de variabile necunoscute. Dacă acest număr este mai mare de trei, atunci problema nu poate fi rezolvată printr-o metodă grafică (există și alte metode eficiente pentru rezolvarea unor astfel de probleme).
3. Regiunea valorilor admisibile ale variabilelor pentru ZLP este în construcție.
4. Se construiește un vector ghid c .
5. Izocelul inițial este trasat prin ODZ (perpendicular pe vectorul de direcție).
6. Se efectuează mișcarea mentală a izocelului inițial în direcția vectorului c, dacă se determină valoarea maximă a funcției obiectiv, sau în sens invers, dacă se determină valoarea minimă a acesteia, până când izoobiectivul devine o referință la ODZ. Punctele de intersecție ale izocelului de referință și ale ODZ vor fi punctele optime ale problemei.
7. Pentru a determina coordonatele punctului optim, este necesar să se rezolve sistemul de ecuații liniare corespunzătoare.
8. Pentru a găsi valoarea optimă a funcției obiectiv, este necesar să înlocuiți valorile optime ale variabilelor în funcția obiectiv și să calculați valoarea acesteia.
20. algoritm grafic. Metoda de rezolvare a problemelor LP
Algoritmul metodei grafice.
1. Prin construirea succesivă a fiecăreia dintre condițiile sistemului de constrângeri ale problemei se realizează construcția ODZ.
2. Vectorul de direcție C este construit de coeficienții pentru variabilele funcției obiectiv.
3. Izocelul inițial este trasat perpendicular pe vectorul de direcție prin origine.
4. Izogolul inițial este mișcat mental în direcția creșterii valorilor vectorului C, dacă se determină valoarea maximă a funcției obiectiv, sau în sens invers, dacă se determină valoarea minimă a acestuia, până când izogolul devine un referire la ODZ. Punctele de intersecție ale izocelului de referință și ale ODZ vor fi punctele optime ale problemei.
5. Pentru a determina coordonatele punctului optim este necesar să se rezolve sistemul de ecuații liniare corespunzătoare acelor condiții la intersecția cărora se află punctul optim.
6. Pentru a găsi valoarea optimă a funcției obiectiv, este necesar să se substituie coordonatele punctului optim în funcția obiectiv și să se calculeze valoarea acesteia.
23. teoreme asupra intervalului de valori admisibile ale problemei LP și asupra funcției obiectiv
Teorema ODZ. Domeniul soluțiilor admisibile ale problemei LP este o mulțime convexă (închisă și mărginită în spațiu n-dimensional)
Teorema 2. Despre funcţia obiectiv a unei probleme de programare liniară.
Funcția obiectiv LLP își ia valoarea optimă la unul dintre punctele de colț ale regiunii valorilor acceptabile ale variabilelor. Dacă funcția obiectiv își ia valoarea optimă în mai multe puncte de colț, atunci ia aceeași valoare în orice punct care este o combinație convexă a acestor puncte de colț.
24. Teorema despre punctul de colț. Suficient și conditie necesara
25. Corolare din teorema privind proprietăţile soluţiilor la problemele LP şi concluzii. Conceptul de linie de bază.
Consecințele din teoreme.
Definiție. Plan = (х1,х2,…,хn), ale căror coordonate pozitive corespund vectorilor liniar independenți, se numește plan de bază PLP .
Consecința 1. Planul de referință nu are mai mult de m coordonate pozitive.
Dacă are exact m coordonate pozitive, atunci un astfel de design de suport se numește nedegenerat, altfel degenerat.
Consecința 2. Fiecare punct de colț al ODZ este un plan de referință.
27. Algoritmul metodei simplex.
La rezolvarea problemelor LP prin metoda simplex, este necesar să se efectueze următoarea secvență de acțiuni.
1. Se verifică dacă problema LP este în formă canonică. Dacă nu, atunci este necesar să convertiți modelul original într-o formă canonică.
2. Pentru acest plan de referință sunt selectate planul de referință inițial și valoarea funcției obiectiv.
3. Se construiește tabelul simplex inițial.
4. Se verifică valorile estimărilor de optimitate din linia indexului. Dacă nu există estimări pozitive, atunci soluția optimă este scrisă și algoritmul își încheie activitatea. În caz contrar, punctul 5 este îndeplinit.
5. În bază se introduce un vector, care corespunde celei mai mari estimări pozitive. Această coloană se numește coloana de activare.
6. Din bază se derivă un vector, care corespunde raportului simplex calculat prin formula 0< Ө ≤ . Данная строка называется разрешающей строкой.
7. Este construit un nou tabel simplex. Se modifică în consecință coloanele B și C B. Restul tabelului este completat față de cel precedent folosind transformări gaussiene, cu rândul index considerat a fi m+1 rânduri și transformat, de asemenea, folosind transformări gaussiene. Se trece la implementarea paragrafului 4 al acestui algoritm.
După construirea fiecărui tabel, puteți verifica corectitudinea calculelor folosind formulele de calcul a estimărilor prezentate în paragraful anterior.
28. Alegerea unei baze și construirea unui plan de referință inițial pentru rezolvarea problemelor prin metoda simplex.
29. Tabele simplex, umplerea lor. Formule pentru calcularea coeficienților rândurilor de index.
30 . Teorema optimității pentru planul unei probleme de programare liniară este o consecință a teoremei de estimare a optimității pentru rezolvarea problemelor prin metoda simplex.
Teorema 1: Dacă pentru un vector  j din sistem
X 1 + a 1 m +1 X m +1 + a 1 m +2 X m +2 + ... + a 1 n X n \u003d a 1
X 2 + a 2 m +1 X m +1 + a 2 m +2 X m +2 + ... + a 2 n X n \u003d a 2
…………………………………………………..
X m + a mn +1 X m +1 + a mn +2 X m +2 + ... + a mn X n = a m
Relația Z j – c j > 0 este îndeplinită, atunci planul X B0 nu este optim și se poate trece la planul X B1 astfel încât Z (X B1) ≤ Z (X B0).
Aici Z j = (С, Â j) este produsul scalar al vectorilor.
C este un vector format din coeficienți la variabilele de bază ale funcției obiectiv Z
 j este un vector format din coeficienții de expansiune ai vectorului corespunzător în termeni de vectori de bază.
c j este coeficientul functiei obiectiv Z cu variabila X j
Consecinţă din teoreme: Dacă pentru toți vectorii  1 ,  2 , …,  n ai unui plan de referință Х relația Z j – c j< 0, то опорный план Х является оптимальным. Величины (Z j – c j) – называются оценками оптимальности соответствующих векторов.
Astfel, teorema și corolarul ne permit să stabilim dacă următorul plan de sprijin este optim și, dacă nu, atunci este necesar să trecem la un alt plan de sprijin, în care valoarea funcției obiectiv va fi mai mică.
cometariu. Teorema și corolarul presupun că problema este în formă canonică cu o funcție obiectiv minimă. Cu toate acestea, metoda simplex poate fi folosită și pentru a rezolva probleme cu o funcție obiectiv maxim. În acest caz, atunci când se analizează valorile estimărilor, se folosește sensul opus al acestora, adică planul va fi optim dacă toate estimările de optimitate sunt nenegative (pozitive sau negative).
31. Alegerea unui vector care intră în bază și care derivă din bază. Relația simplex.
Pentru a trece la un nou plan de referință, este necesar unul dintre vectorii liberi 
intră în bază și scoate unii dintre vectorii de bază. Pentru a introduce în bază, alegem un vector care are cel puțin o coordonată pozitivă. Fie vectorul A m+1 un astfel de vector.
descompunere -
Resp. vector, pisica. va fi un plan de referință dacă coordonatele sale sunt nenegative, iar numărul de coordonate pozitive va fi egal cu m.
Coordonatele vectoriale X1 trebuie să fie nenegative, adică .
În cazul în care un 
, atunci această coordonată va fi nenegativă.
Fie ca minimul din relația (5) să se obțină la i =1, atunci dacă luăm
apoi prima coordonată a vectorului 1 X va deveni zero.
Relația (6) se numește relație simplex. Astfel, ne-am mutat de la linia de bază originală 0 X(vectori de bază A1, A2, ... Am) la planul de referință 1 X(vectori de bază А2,А3,…,Аm, Am+1).
32. element permisiv al mesei, alegerea acestuia. Regula de eliminare completă a lui Jordan pentru recalcularea tabelului simplex.
33. Regula patrulatera pentru recalcularea tabelului simplex
34. Un semn al unicității planului optim, a setului de planuri optime și a absenței unui plan optim la rezolvarea problemei LP prin metoda simplex.
La rezolvarea problemelor prin metoda simplex, sunt posibile următoarele tipuri de soluții optime:
1. Unicitatea . Dacă estimările tuturor vectorilor liberi sunt strict negative, atunci proiectul de suport obținut este optim și unic. (vezi exemplul din paragraful anterior).
2. Optim alternativ (set de soluții optime).
Dacă printre estimările nepozitive ale vectorilor liberi există cel puțin o estimare zero, atunci proiectul suport obținut va fi optim, dar nu singurul. În acest caz, puteți merge la alte planuri de sprijin (vectorii care corespund estimărilor zero sunt introduși în bază) și, apoi, scrieți soluția optimă generală ca o combinație convexă a planurilor de sprijin optime obținute.
3. LLP nu are o soluție optimă, deoarece funcția obiectiv nu este mărginită de jos . Dacă tabelul simplex are un scor pozitiv și toate elementele coloana dată sunt negative și zero, atunci acest vector poate fi introdus în bază. Cu toate acestea, niciunul dintre vectorii de bază nu poate fi dedus din bază. De aici rezultă că o scădere suplimentară a funcției obiectiv este posibilă atunci când se trece la un plan nesuportator.
4. LLP nu are o soluție optimă, deoarece sistemul de constrângeri este inconsecvent. Deoarece la rezolvarea LLP, metoda simplex obișnuită ar trebui să fie planul de referință inițial, sistemul de ecuații liniare nu este cu siguranță inconsecvent. Prin urmare, un astfel de caz nu poate apărea atunci când se rezolvă prin metoda simplex obișnuită.
5. Dacă ODZ constă dintr-un punct, atunci soluția unei astfel de probleme este banală și poate fi obținută fără a utiliza metoda simplex.
35. Când se utilizează metoda bazei artificiale?
artificial.
36. Construirea problemei M în metoda bazei artificiale
Dacă problema de programare liniară este în formă canonică, totuși, nu toate ecuațiile conțin variabile de bază, adică nu există o linie de bază inițială. În acest caz, în acele ecuații în care nu există variabile de bază, este necesar să se adauge o variabilă nenegativă cu un coeficient de +1. O astfel de variabilă este numită artificial.
La funcția obiectiv trebuie adăugată o variabilă artificială cu un număr pozitiv foarte mare (deoarece funcția obiectiv este de a găsi minimul). Acest număr este notat cu litera latină M. Poate fi considerat egal cu +∞. În acest sens, uneori metoda pe bază artificială se numește metoda M. O astfel de transformare a problemei inițiale se numește construcția problemei extinse. Dacă rezolvați o problemă cu o funcție obiectiv pentru a găsi o variabilă artificială, trebuie să adăugați la funcția obiectiv un număr pozitiv foarte mare (deoarece funcția obiectiv este de a găsi minimul). Acest număr este notat cu litera latină M. Poate fi considerat egal cu +∞. În acest sens, uneori metoda pe bază artificială se numește metoda M. O astfel de transformare a problemei inițiale se numește construcția problemei extinse. Dacă o problemă este rezolvată cu o funcție obiectiv pentru a găsi maximul, atunci variabilele artificiale intră în funcția obiectiv cu un coeficient -M.
Astfel, în problema extinsă, avem o linie de bază (deși unele dintre variabilele de bază sunt artificiale).
Se construiește tabelul simplex inițial.
37. construirea unei linii index în metoda bazei artificiale
Este construit un tabel inițial simplex, în care rândul index este împărțit în două rânduri, deoarece estimările constau din doi termeni. Linia de sus conține termenul estimării fără M, linia de jos arată coeficienții lui M. Semnul estimării este determinat de semnul coeficientului lui M, indiferent de valoarea și semnul termenului fără M, deoarece M este un număr pozitiv foarte mare.
Astfel, pentru a determina vectorul care este introdus în bază, este necesar să se analizeze linia inferioară a indicelui. Dacă un vector artificial este derivat din bază, atunci coloana corespunzătoare din tabelele simplex ulterioare poate fi omisă dacă nu este nevoie să se obțină o soluție la problema duală (vezi subiectul următor).
După ce toți vectorii artificiali au fost scoși din bază, rândul de jos va avea toate elementele zero, cu excepția estimărilor corespunzătoare vectorilor artificiali. Ele vor fi egale cu -1. O astfel de linie poate fi eliminată din considerare și soluția ulterioară poate fi efectuată prin metoda simplex obișnuită, dacă nu este nevoie să obțineți o soluție la problema duală (vezi subiectul următor).
38. Criteriul optimității în metoda bazei artificiale. Semnul este construcția planului de bază inițial al sarcinii inițiale.
39. Algoritmul metodei dual simplex
Algoritmul metodei dual simplex:
1. în mod obişnuit completați primul tablou simplex, ignorând semnele termenilor liberi. Se crede că o astfel de problemă ar trebui să aibă o bază de unitate inițială.
2. Selectați linia de ghidare după cel mai mare element negativ absolut al coloanei de membri liberi A0
3. Coloana de ghidare este selectată în funcție de cea mai mică valoare absolută a raportului dintre elementele liniei index și elementele negative ale liniei de ghidare.
4. Recalculați tabelul simplex conform regulii eliminărilor complete Jordan
5. verifica admisibilitatea planului primit. Un semn al obținerii unui plan de referință acceptabil este absența elementelor negative în coloana A0. Dacă există elemente negative în coloana A0, atunci mergeți la al doilea paragraf. Dacă nu există, atunci ei procedează la rezolvarea problemei în mod obișnuit.
6. Un semn al obținerii unei soluții optime prin metoda dual simplex este criteriul de optimitate pentru metoda simplex obișnuită.
41. Modele de transport deschise și închise. Trecerea de la un model de transport deschis la unul închis.
Tipuri de sarcini de transport.
Disponibil m furnizori de produse omogene cu stocuri cunoscute de produse si n consumatorii acestor produse cu volume date de nevoi. Sunt cunoscute și costurile unitare ale transportului.
Dacă suma volumelor stocurilor de produse este egală cu volumul nevoilor tuturor consumatorilor, atunci o astfel de problemă se numește sarcina de transport inchisa
(adică dacă ∑ Ai = ∑ Bj), altfel problema transportului se numește deschis. Pentru a rezolva problema de transport este necesar ca acesta sa fie inchis.
O sarcină de transport deschisă poate fi convertită într-una închisă în felul următor.
Fie ∑Ai > ∑Bj. În acest caz, este necesar să se introducă un consumator fictiv n + 1 cu un volum de nevoi ∑Ai – ∑Bj Costurile unitare pentru transportul de la furnizori la un consumator fictiv sunt presupuse a fi 0, deoarece de fapt un astfel de transport nu va fi efectuate și o parte din produse vor rămâne la furnizori.
Dacă ∑Bj > ∑Ai . În acest caz, este necesară introducerea unui furnizor fictiv m + 1 cu volumul de inventar ∑Bj – ∑Ai . Costurile unitare ale transportului de la un furnizor fictiv la consumatori sunt presupuse a fi egale cu 0, deoarece de fapt un astfel de transport nu va fi efectuat și consumatorii nu vor primi unele dintre produse.
42. Metode de construire a distribuţiei iniţiale în problema transportului: metoda colţului de nord-vest şi metoda celui mai mic element din matrice.
Tehnica nord-vestică pentru construirea unui plan de referință. Conform acestei tehnici, formarea valorilor de trafic începe cu s.-z. colțul mesei, adică din celula x11. Conform acestei metode, în primul rând, se distribuie bunurile primului furnizor. Mai mult decât atât, primul furnizor îl satisface pe primul consumator cât mai mult posibil. Apoi, dacă furnizorul mai are marfa,
Metoda celui mai mic element din matrice.
Esența metodei constă în faptul că oferta maximă posibilă este întotdeauna pusă în celulă, ceea ce corespunde celui mai mic tarif al matricei.
În primul rând, facem semne (de exemplu, cu semnul ▼) în acele celule ale liniilor în care se observă cel mai mic preț pentru linie. Apoi ocolim masa pe coloane si facem aceleasi note in celulele in care cel mai mic pret este pe coloane.
O distribuție ulterioară se face mai întâi pe cât posibil pe celule cu două mărci, apoi cu unul, iar apoi sarcina este reechilibrată la (m + n - 1) umpluturi. Organizam umpluturile atunci cand trecem masa de la stanga la dreapta si de sus in jos.
43. Proprietăţile sarcinilor de transport
Problema transportului are unele proprietăți care pot fi reflectate în următoarele teoreme.
Teorema 1. O problemă de transport închis are întotdeauna o soluție.
Teorema 2. Dacă volumul stocurilor de produse și volumul nevoilor sunt numere întregi, atunci soluția problemei transportului va fi și ea întreagă.
Teorema 3. sistemul de constrângeri al unei probleme de transport închis este întotdeauna dependent liniar.
Din această teoremă rezultă că distribuția unei probleme de transport închisă are întotdeauna m + n – 1 variabile de bază și (m – 1) (n – 1) variabile de timp liber.
44. Distribuție degenerată în problemele de transport, scăpând de degenerescență. Combinație tăiată.
Distribuția se numește degenerată dacă numărul de celule este mai mic decât m + n - 1.
45. Teoreme de optimitate pentru problema transportului.
Teorema. Dacă pentru o oarecare repartizare a sarcinii de transport tu
sunt indeplinite conditiile:
A). ui+vj = cij pentru celulele ocupate
b) ui+vj ≤ сij, pentru celule libere,
atunci această distribuție este optimă.
Valorile ui se numesc potențiale de rând, iar valorile vj se numesc potențiale de coloană.
46. Potențialele și metodele de calcul ale acestora.
Pentru a afla potențialele rândurilor și coloanelor se folosește următorul raționament, bazat pe condiția a) a teoremei optimității.
Numărul de ecuații bazate pe această condiție este m + n – 1, iar numărul de necunoscute ui și vj este m + n. Acea. numărul de variabile este mai mare decât numărul de ecuații și toate ecuațiile sunt liniar independente. Soluția unui astfel de sistem de ecuații liniare este nedefinită, așa că unuia dintre potențiale trebuie să i se atribuie orice valoare. În practică, ui = 0. se obţine un sistem de m + n – 1 ecuaţii cu m + n – 1 variabile necunoscute. Acest sistem poate fi rezolvat prin orice metodă. În practică, pentru calcularea potențialelor, se iau în considerare celulele ocupate, pentru care se cunoaște unul dintre potențialele lor, iar pe baza condiției a) a teoremei se calculează valorile potențialelor necunoscute rămase.
47. Calculul estimărilor optimității repartizării sarcinilor de transport și criteriul optimității.
Pe baza relației b) a teoremei, putem scrie următoarea formulă de calcul a estimărilor: δ ij= ui + vj – сij. Pentru a nu confunda estimările cu volumele de trafic, acestea (estimările) sunt încadrate în cercuri.
Estimările de optimitate în celulele TK libere sunt un criteriu de optimitate, care este utilizat pentru a verifica distribuția pentru optimitate. Dacă estimările tuturor celulelor libere sunt mai mici sau egale cu zero, atunci această distribuție este optimă.
48. redistribuirea proviziilor în problema transporturilor
Dacă distribuția nu este optimă, atunci este necesară redistribuirea proviziilor.
Pentru redistribuire, se construiește un ciclu de recalculare. Celula cu cel mai mare scor pozitiv este selectată ca celulă. Această celulă este marcată cu semnul „+”, adică este necesar să se înregistreze o anumită cantitate de livrare în ea. Dar apoi echilibrul din această coloană va fi perturbat, prin urmare, una dintre celulele ocupate ale acestei coloane trebuie să fie marcată cu semnul „-”, adică volumul de aprovizionare ar trebui să fie redus cu aceeași sumă. Dar apoi echilibrul pentru această linie se va schimba, prin urmare, o celulă ocupată a acestei linii trebuie să fie marcată cu semnul „+”. Acest proces continuă până când un semn „-” este plasat pe linia în care a fost localizată celula originală.
Pentru orice celulă liberă există un ciclu de recalculare și, în plus, singurul.
49. lanțuri de redistribuție, tipurile acestora.
Fie ca planul de transport luat în considerare să nu fie optim, adică există estimări relative pozitive. Apoi se ia o celulă nefavorabilă (una dintre cele nefavorabile) și se construiește un ciclu de recalculare pentru aceasta, conform căruia transportul planificat este apoi redistribuit. Ciclul este construit sub forma unei linii închise întrerupte, ale cărei segmente se desfășoară fie de-a lungul coloanei, fie de-a lungul liniei. Într-unul din colțurile liniei întrerupte se află o celulă nefavorabilă care revendică produsul, iar în celelalte colțuri celulele sunt umplute, adică. atunci când construim un ciclu, pornim de la celula candidată și revenim la ea de-a lungul unei linii întrerupte, dar putem face doar ture în celulele umplute (corespunzând variabilelor de bază). Lasă o celulă nefavorabilă să revendice produsul Q. Pentru a preveni un dezechilibru în tabel, este necesar să
adăugați și scădeți Q la traficul disponibil. Deoarece există un număr par de colțuri, Q va fi adăugat în jumătate din celule și scăzut în cealaltă jumătate. Ciclul este pornit în sensul acelor de ceasornic sau în sens invers acelor de ceasornic din celula candidată, plasând acolo Q bun, apoi Q este scăzut din celula vecină, apoi adăugat și așa mai departe. Valoarea lui Q în sine este aleasă astfel încât una dintre celule să fie golită, dar niciuna dintre provizii nu ar deveni negativă.
Pentru a face acest lucru, Q trebuie ales egal cu cel mai mic reductibil dintre celulele din care se scade Q. În fig. 7.1 și 7.2 vom arăta exemple de cicluri și regula de calcul.
În acest caz, două celule sunt golite. Dar este necesar ca o singură celulă să devină reciproc goală. Ei fac asta: una dintre celulele de golire este golită în noul tabel, iar zero este pus în cealaltă celulă de golire. Această celulă este considerată de bază (umplută) în noul tabel.
50. Alegerea volumului de redistribuire.
Determinarea volumului de produse transportate. La determinarea volumului de produse deplasate prin ciclul de numărare, trebuie să pornim de la următoarele două considerații:
a) după transformarea în celulele tabelului nu se obțin numere negative;
b) una dintre celulele ocupate trebuie să devină liberă.
Pentru ca aceste condiții să fie îndeplinite, este necesar să se selecteze volumul produselor transportate astfel: θ=min (хij) -, unde (хij) este volumul de transport din celulele ciclului de recalculare marcate cu „ -" semn.
θ = min(20;30)=20
θ se adaugă la valorile celulelor marcate cu semnul „+”. θ se scade din valorile celulelor marcate cu semnul „-”. Valoarea de aprovizionare a celulelor rămase este suprascrisă fără modificări. Ca rezultat, obținem următorul tabel.
53. Algoritmul metodei potenţialelor.
Algoritm:
1. Verificați dacă ecuația este satisfăcută pentru sarcină 
dacă nu, un furnizor sau un consumator fictiv este introdus în sarcină
2. Condiția sarcinii este scrisă sub forma unui transport.tabel
3. Se construiește o linie de bază inițială
4. Se determină potențialele de aprovizionare și consumatori
5. Scorurile celulelor libere sunt calculate. Dacă toate nu sunt negative, planul este optim și trebuie să scrieți răspunsul. Matricea de transport X și determină valoarea costurilor de transport. Dacă planul nu este optim, adică printre estimări există unele negative, atunci alegeți o celulă promițătoare cu cea mai mare valoare negativă. estimați și treceți în mărime la următorul.
6. Încărcați o celulă de perspectivă. Pregătiți un nou plan de bază sub forma unei mese de transport. Treci la punctul 4.
54. Contabilitatea costului de producție și transport al produselor. Sarcina de transport cu interdicții de aprovizionare.
La rezolvarea unor probleme, este necesar să se țină cont de costurile nu numai pentru transportul mărfurilor, ci și pentru producerea produselor transportate. Pentru a face acest lucru, în matricea transp. sarcini
Unde Cij ' este costul redus de producere a unei unități de producție.
Cij „- costul transportului unei unități de producție.
Sarcini cu interdicții de aprovizionare.
În unele situații, nu este posibilă transportul produselor pe nicio rută.
Pentru a face acest lucru, în matricea sarcinii de transport, transportul prin care este interzis, se introduce tariful prohibitiv M. În continuare, sarcina este rezolvată în mod obișnuit., totuși, această celulă va corespunde întotdeauna unui scor negativ al celulei. .
55. ținând cont de restricțiile privind circulația rutelor, ținând cont de caracterul obligatoriu al anumitor livrări în problema transportului.
ținând cont de restricțiile privind trecerea rutelor.
În unele sarcini de transport, pe unele rute, o mai mică debitului decât este necesar pentru a satisface cererea punctului de consum.
tinand cont de caracterul obligatoriu al anumitor livrari in problema transportului.
În unele cazuri, sarcina necesită ca, de exemplu, de-a lungul traseului Ak Bs, livrarea în unități de volum A trebuie efectuată. În acest caz, din volumul de producție al punctului A și din volumul S Bs se scad aprovizionarea obligatorie și se rezolvă problema cu privire la aprovizionarea opțională. După obținerea soluției optime, alimentarea se adaugă în mod necesar la volumul aflat în celula Ak Bs.
56. Posibile concluzii cu economice. interpretarea distribuţiei optime pentru probleme de transport deschis.
La primirea distribuției optime, este necesar să reveniți la problema inițială și să faceți cea mai economică corespunzătoare. constatări. Acestea sunt următoarele:
1. Dacă se introduce un punct de consum, aceasta înseamnă că în sistemul analizat există volume de producție excesive și este posibilă, fără a aduce atingere sistemului în cauză, să se reducă capacitățile acelor puncte de producție cu valoarea obligatorie. care sunt legate de punctul fictiv al consumului.
2. Dacă se introduce un punct de producție fictiv, atunci aceasta înseamnă că capacitățile punctelor reale de producție nu sunt suficiente și trebuie crescute. Se mărește capacitatea acelor puncte de producție care sunt cele mai apropiate de punctele de consum legate de punctul de producție fictiv. Capacitatea producătorului este mărită cu valoarea obligatorie. Pentru a face acest lucru, luați în considerare coloana punctului de consum, care este legat de punctul fictiv de producție și găsiți cel mai mic tarif din acesta. Cel mai eficient este creșterea capacității punctului de producție corespunzător acestui tarif cu valoarea obligatorie.
57. Conceptul de dualitate. Formularea economică a problemelor duale pe exemplul problemei optimizării planului de producție.
Problema duală este o problemă auxiliară de programare liniară formulată folosind anumite reguli direct din condițiile problemei inițiale, sau directă.
Să existe o sarcină de optimizare a planului de producție. Arata cam asa:
Sarcina inițială:
a 11 x 1 + a 12 x 2 +…+ a 1p x p ≤v 1 | 1
a 21 x 1 + a 22 x 2 +…+ a 2p x p ≤v 2 | la 2
……………….. |.. (1)
A t 1 x 1 +a t 2 x 2 + ... + a t n x n ≤v 1 | la t
x j ≥0, j = 1,n(2)
z = c 1 x 1 +c 2 x 2 +…+c n x n ->max(3)
X \u003d (x 1, x 2, ..., x n)
a ij - numărul de materii prime de al-lea tip, cheltuit pentru producerea celui de-al-lea tip de produs
Problemă dublă
Lăsați întreprinderea din orice motiv să nu poată produce produse. Pentru a reduce costul perioadelor de nefuncționare, compania poate vinde materiile prime pe care le are. La ce preț ar trebui vândute materiile prime?
i - prețul celui de-al i-lea tip de materie primă disponibilă la întreprindere.
a 11 y 1 + a 21 y 2 + ... + a t 1 y t≥s 1
a 12 x 1 + a 22 y 2 + ... + a t 2 x n ≥s 2
……………….. (1’)
A 1p y 1 +a 2p y 2 +…+ a tp la t≥s P
i ≥0, j = 1,m(2’)
F = b 1 y 1 +b 2 y 2 +…+b m y m ->min(3’)
58. Corespondența dintre elementele structurale ale problemelor directe și duale
Fiecare problemă de programare liniară poate fi asociată
sarcină dublă conform următoarelor reguli:
1. În toate constrângerile problemei inițiale, termenii liberi trebuie
fie în dreapta, iar termenii cu necunoscute în stânga.
2. Constrângerile-inegalitățile problemei inițiale trebuie să aibă semne,
îndreptată într-o singură direcție.
3. Dacă funcția obiectiv din problema originală este minimizată, constrângerile de inegalitate trebuie scrise cu semnul „≤”, atunci în problema duală funcția obiectiv va fi minimizată și semnele constrângerilor de inegalitate vor fi „≥”.
4. Fiecare constrângere a problemei originale corespunde unei variabile în
sarcină dublă. Dacă o variabilă corespunde unei inegalități, este nenegativă, dacă corespunde egalității, atunci variabila este fără restricții asupra semnului („arbitrare”).
5. Coeficienții variabilelor din constrângerile problemei duale se obțin prin transpunerea matricei compuse din
coeficienți pentru variabilele problemei inițiale.
6. Termenii liberi ai problemei inițiale sunt coeficienții la
variabile în funcția scop a problemei duale și libere
termenii din problema duală sunt coeficienții variabilelor din
funcţiile problemei iniţiale.De asemenea, observăm că relaţia de dualitate este reciprocă, adică. sarcina duală faţă de cea duală coincide cu cea iniţială.Perechile duale de sarcini se împart în simetrice şi asimetrice. Într-o pereche simetrică, constrângerile problemelor primale și duale sunt inegalități non-strictive și, prin urmare, variabilele ambelor probleme pot lua doar valori nenegative.
59. Construirea problemelor duale la problemele originale scrise în forma standard, canonică și generală a modelului (construcție de probleme duale simetrice și asimetrice)
Formular standard (original)
Σ a ij x j ≤ b i , i=1,n(1)
x j ≥0, j=1,n(2)
z = Σ c j x j ->max(3)
Standard dublu
Σ a ij y i ≤ c j , j=1,n(1)
yi ≥0, j=1,m(2)
F = Σ b i y i ->min(3)
Problema originală în formă canonică:
Σ a ij x j = b i , i=1,m(1)
x j ≥0, j=1,n(2)
z = Σ c j x j ->min(3)
Dual canonic
Σ a ij y i ≤ c j , j=1,n(1)
y i - oricare (2)
F = Σ b i y i ->max(3)
Să oferim o interpretare economică a unei perechi de probleme duale. Luați în considerare problema utilizării raționale a resurselor. Lăsați întreprinderea să aibă resurse b1,b2,...bm care pot fi utilizate pentru a produce n tipuri de produse. Să fie cunoscut și costul unei unități de produs de tip j cj (j=1,n) și rata de consum al i-a resursă (i=1,m) pentru producerea unei unități. j-a producție– aij.Se cere determinarea volumului de productie a fiecarui tip xj (j=1,n), maximizand costul total
f= c1x1+…+cnxn (1)
În același timp, consumul de resurse nu trebuie să depășească disponibilitatea acestora:
a11x1+…+a1nxn<=b1 }
…………………….. } (2)
am1x1+…+amnxn<=bm }
Toate cunoscute în sensul lor economic sunt nenegative:
Xj>=0 (j=1,n). (3)
Rețineți că această problemă formează o problemă duală simetrică.
Probleme duble asimetrice.
Să luăm ZLP la maximum în forma canonică:
Max Z=(n;j=1)Σcj*xj
(n;j=1)Σaij*xj=bi (i=1,m)
Xj>=0 (j=1,n).
60. Teorema principală și a doua a dualității (teoreme de stare și explicați)
Prima teoremă a dualității.
Teorema: daca una dintre problemele duale are un plan optim, atunci cealalta este rezolvabila, i.e. are un plan opt. În acest caz, valorile extreme ale funcțiilor obiectiv coincid (j=de la 1 la n) Σcjxj*= (i=de la 1 la m)Σbiyi* dacă în original. problema functia obiectiv este nelimitata pe multimea de planuri, apoi in problema duala sistemul de constrangeri este inconsecvent.
A doua teoremă a dualității și interpretarea ei economică.
Pentru a solutii valabile perechile de probleme duale au fost optime, este necesar și suficient să se îndeplinească condiția: xj*(∑aij yi*-cj)=0, j de la 1 la n, yi*(∑aij xj*-bi)=0, I de la 1 la m. Acestea sunt condiții de slăbiciune complementară. Din ele rezultă: dacă orice restricție a problemei duale este convertită de planul optim în egalitate strictă, atunci componenta corespunzătoare a optului. planul problemei duale ar trebui să fie egal cu zero.Dacă unele componente opt. plan este egal cu zero, atunci restricția corespunzătoare a problemei duale este convertită de opt.plan într-o egalitate strictă xj*>0, deci (i= de la 1 la m)Σaij yi*=cj opt.plan, atunci dacă costuri>prețuri, volum de producție=0 Σaij yi* >cj deci xj*=0
yi*>0 deci (j=de la 1 la n) Σaij xj*=bi (rase de resurse = stoc de resurse).
(j=1 la n) Σaij xj* Sensul teoremei este următorul: Dacă estimarea costului consumului de resurse pentru producția unei unități de prod-ii \u003d preț, atunci acest tip de prod-ii este inclus în planul optim; Dacă costurile depășesc prețul, atunci prod-yu nu ar trebui să fie produs; Dacă consumul de resurse = stoc, atunci estimarea costului acestei resurse este pozitivă. O astfel de resursă se numește limitată. Cel mai deficitar.res-s are cel mai mare scor; Dacă resursa nu este cheltuită în totalitate, atunci costul estimat al acesteia = 0. 61. Construirea planului optim de suport pentru problema duală din tabelul simplex al problemei originale Informații din coloanele matricei inverse a transformărilor liniare care au condus la rezultatul optim. Coloanele matricei D-1 oferă informații foarte utile. Coloana A3: prețul „umbră” al resursei S2 este y01=0, coloana rămâne singur și din prima linie se poate citi că x3=9, adică. la implementarea planului optim găsit, prima resursă va fi în exces, iar acest exces (subutilizare) se va ridica doar la 9 unități convenționale. Coloana A4: prețul „umbră” al resursei S2 este egal cu y02=1, resursa va fi utilizată pe deplin și eventuala ei creștere va duce la o creștere a funcției obiectiv (adică venit). Și pentru că y02=1, apoi creșterea resursei S2 cu 1 c.u. va da o adunare în termeni de venit prin.Z = y02· .w2 = = 1.1 = 1 (mii UAH) (aici.w2 este incrementul resursei S2 și .Z este incrementul corespunzător al venitului). Cu o astfel de creștere a resursei S2, venitul maxim va fi deja Zmax=58 mii UAH. + 1 mie UAH = 59 mii UAH. Pe fig. 6.2 ilustrează această situație, comentariu despre care va fi dat mai jos. Din coloana A4 mai rezultă că cu o creștere a resursei S2 cu 1 c.u. pentru noul punct optim, producția de mărfuri T1 va scădea cu ½ tonă (la intersecția dintre rândul variabilei de bază x1 și coloana A4 există „-1/2”), iar producția de mărfuri T2 va crește cu 3/2 tone (deoarece în rândul cu variabila de bază x2 din coloana A4 avem „3/2”. Ceea ce s-a spus despre coloana A4 va fi comentat mai jos folosind construcții grafice (Fig. 6.2). Coloana A5: „ prețul umbră” al resursei S3 este egal cu y03=2. Aceasta înseamnă că o creștere a resursei S3 cu 1 c.u. va aduce un plus în Z la.Z = y03 · .v3 = 2.1 =2(mii grivne) și va fi Zmax=58 mii grivne. + 2 mii UAH = 60 mii UAH. În același timp, după cum urmează din coloana A5 din tabel. 3, producția lui T1 va crește cu ½ tonă și T2 va scădea cu ½ tonă. Stocul de materii prime S1 (vezi linia 1) va creste cu 3/2 uc. 62. Ideea metodei de programare dinamică și interpretarea ei geometrică. Principiul optimității lui Bellman. Soluția optimă a problemei prin metoda programării dinamice se găsește pe baza ecuației funcționale Pentru a-l defini, aveți nevoie de: 1. notați ecuația funcțională pentru ultima stare a procesului (corespunde cu l \u003d n-1) fn-1(Sl-1)=optim (Rn(Sn-1,Un)+f0(Sn)) 2. găsiți Rn(Sn-1,Un) dintr-o mulțime discretă a valorilor sale pentru unele fixe Sn-1 și Un din zonele admisibile corespunzătoare (deoarece f0(Sn)=0, apoi f1(Sn-1)= optim(Rn(Sn-1,Un) Ca urmare, după primul pas, se cunosc soluția Un și valoarea corespunzătoare a funcției f1(Sn-1) 3. Scădeți valoarea lui l cu una și notați ecuația funcțională corespunzătoare. Pentru l=n-k (k= 2,n) arată ca fk(Sn-k)=optim (Rn-k+1(Sn-k,Un-k+1)+fk-1(Sn-k+1)) (2) 4. găsiți o soluție optimă condiționat pe baza expresiei (2) 5. se verifică cu ce este egală valoarea lui l. Dacă l=0, calculul soluțiilor optime condiționat este finalizat și se găsește soluția optimă a problemei pentru prima stare a procesului. Dacă l nu este egal cu 0, treceți la pasul 3. 6. Calculați soluția optimă a problemei pentru fiecare etapă ulterioară a procesului, trecând de la sfârșitul calculelor la început. Metoda dinamismului programelor permite înlocuirea unei probleme cu multe variabile cu un număr de probleme rezolvate succesiv cu un număr mai mic de variabile. Decizia se ia pas cu pas. Principiul principal pe care se bazează optimizarea unui proces în mai multe etape, precum și caracteristicile metodei de calcul, este principiul optimității Bellman. Comportamentul optim are proprietatea că oricare ar fi starea inițială și decizia inițială, deciziile ulterioare trebuie să fie optime în raport cu starea rezultată din decizia inițială. Din punct de vedere matematic, se scrie ca o expresie a formei: fn-1(Sl)=optim (Rl+1(Sl,Ul+1)+fn-(l+1)(Sl+1)) (1) (l=0,n-1)Optim în expresie înseamnă maxim sau minim în funcție de starea problemei. 63. Cerințe pentru problemele rezolvate prin metoda DP Programarea dinamică este o metodă matematică de găsire a soluțiilor optime la problemele cu mai mulți pași. Un proces în mai multe etape este un proces care se dezvoltă în timp și se descompune într-un număr de pași sau etape. Una dintre caracteristicile metodei de programare dinamică este că deciziile luate în legătură cu procesele în mai multe etape sunt considerate nu ca un singur act, ci ca un întreg complex de decizii interdependente. Această succesiune de decizii interconectate se numește strategie. Scopul planificării optime este alegerea unei strategii care să ofere cel mai bun rezultat în ceea ce privește un criteriu preselectat. O astfel de strategie se numește optimă. O altă caracteristică importantă a metodei este independența deciziei optime luate la pasul următor din preistorie, adică. asupra modului în care procesul care este optimizat a atins starea actuală. Soluția optimă este aleasă doar luând în considerare factorii care caracterizează procesul în acest moment. Metoda programelor dinamice se caracterizează și prin faptul că alegerea soluției optime la fiecare pas trebuie făcută ținând cont de consecințele acesteia în viitor. Aceasta înseamnă că, în timp ce optimizați procesul la fiecare pas individual, în niciun caz nu trebuie să uitați de toți pașii următori. 64.Formularea economică și construcția unui model matematic al problemei rezolvate prin metoda DP (pe exemplul problemei distribuției investițiilor de capital). Relația de recurență Bellman. Să explicăm în prealabil că metoda de programare dinamică se aplică în primul rând acelor probleme în care procesul (sau situația) care este optimizat este desfășurat în spațiu sau timp, sau ambele. Procesul (situația) în sine să fie atât de complicat încât nu există nicio modalitate de a-l optimiza folosind metode cunoscute. Apoi, conform metodei de programare dinamică, un proces COMPLEX (operație, situație) este împărțit (partiționat) într-un număr de etape (etape). Această defalcare este în multe cazuri firească, dar în cazul general este introdusă artificial. .
De exemplu, când luăm în considerare orice joc de șah, orice mișcare a fiecărui jucător servește doar împărțirea întregului lot în etape (etape) separate. Și într-o operațiune militară de urmărire a unei rachete împotriva alteia, întregul proces continuu trebuie să fie împărțit artificial în etape, de exemplu, fiecare secundă de observație. Metoda de programare dinamică permite ca optimizarea întregului proces complex să fie înlocuită cu optimizarea condiționată pentru fiecare dintre etape. (etape) urmate de sinteza controlului optim al întregului proces. În același timp, metoda prevede că optimizarea condiționată la o etapă (etapă) separată se face în interesul, în primul rând, al întregii operațiuni. Toate calculele care fac posibilă găsirea valorii optime a efectului obținut în n pași, fn(S0), sunt efectuate conform formulei (1), care se numește ecuația funcțională Bellman de bază sau relația de recurență. La calcularea următoarei valori a funcției fn-1 se folosește valoarea funcției fn-(l+1) obținută la pasul anterior, iar valoarea directă a efectului Rl+1(Sl,Ul+1), realizată ca urmare a alegerii soluţiei Ul+1 pentru sistemele Sl de stare dată. Procesul de calcul al valorii funcției fn-1(l=0,n-1) Se realizează în condiția inițială naturală f0(Sn)=0, ceea ce înseamnă că în afara stării finale a sistemului, efectul este zero. 65. Problema repartizării investițiilor de capital (exemplu). Pentru a rezolva problema distribuției optime a investițiilor de capital, vom folosi ecuația funcțională Bellman. Mai întâi, folosind cea mai simplă situație, vom ilustra derivarea ecuației funcționale Bellman, iar apoi, folosind un exemplu, vom demonstra cum să folosim această ecuație pentru a rezolva problema care ne interesează. Să începem cu distribuția optimă a investițiilor de capital alocate în valoare de K între două întreprinderi. Compartimentele de planificare ale întreprinderilor, pe baza calculelor lor, au format funcțiile de venit q(x) pentru întreprinderea P1 și h(x) pentru întreprinderea P2. Aceste funcții înseamnă că dacă prima sau a doua întreprindere primește o investiție în valoare de x, atunci prima întreprindere se va primi venitul q(x), iar al doilea h(x), iar valoarea lui x poate lua valori continue sau discrete cunoscute de la 0 la K. Deci, fie compania P1 a alocat investiții de capital în suma x, apoi companiei P2 i se alocă suma K - x. În acest caz, venitul q(x) va fi primit de la prima întreprindere, iar h(K - x) de la a doua. Dacă investițiile K au fost alocate pentru o perioadă de planificare, atunci venitul total din cele două întreprinderi va fi R(K, x) = q(x) + h(K - x). Evident, x și, în consecință, K - x trebuie alese astfel încât R(K, x) să-și ia valoarea maximă, pe care o notăm cu F(K): Această intrare este ca un schelet pentru intrări mai complete. ecuația funcțională Bellman. COMPLICAȚI sarcina noastră distribuind investițiile de capital pe două perioade de planificare (două etape) .
Să se decidă inițial să se aloce suma x primei întreprinderi P1 și x celei de-a doua întreprinderi P1. În general, venitul ar fi egal cu R(K, x) = q(x) + h(K - x). Dacă avem în vedere că investițiile sunt distribuite pe 2 perioade (2 etape), atunci la prima întreprindere soldul investițiilor va fi x, unde , iar la a doua - .(K - x), unde, în consecință, venitul pentru a doua perioadă va fi q( .x) - conform primei facilitati și h[.(K - x)] - conform celei de-a doua. Optimizarea dinamică a programării, de regulă, începe de la etapa finală. Prin urmare, pornim de la a doua etapă, notând F1 venitul maxim posibil de la două întreprinderi în a doua etapă. obține Apoi, la ultima etapă considerată (în cazul nostru, a doua), adunăm cumva etapa anterioară (în cazul nostru, prima) și găsim venitul maxim din cele două etape împreună: În mod similar, pentru n etape, obținem unde Fn-1 este funcția obiectiv care dă cel mai bun rezultat pentru ultimele (n - 1) etape. Ecuația funcțională Bellman rezultată este recurentă, adică. asociază valoarea Fn cu valoarea Fn-1. Mai general, ecuația Bellman are forma unde , Fn-1 - venitul maxim pentru (n - 1) ultimele etape, Fn - venitul maxim pentru toate cele n etape. 66. Conceptul de rezolvare a problemelor de programare neliniară Să se pună problema programării neliniare în următoarea formă generală: găsiți astfel de valori ale variabilelor x1, x2, ..., xn care îndeplinesc condițiile: și aduceți extremul necesar (maxim sau minim) al funcției obiectiv f = f(x1, x2,…, xn), (13.2) unde f(х1, …, хn) și qi(х1, …, хn) (m , 1 i =) sunt reale neliniare, funcții regulate ale n variabile reale. Conform proprietăților lor generale, problemele de programare neliniară pot semnificativ diferite de cele liniare. De exemplu, domeniul soluțiilor fezabile poate fi deja neconvex, iar extremul funcției obiectiv poate fi observat în orice punct al domeniului fezabil. Metodele de rezolvare a problemelor neliniare diferă, de asemenea, semnificativ. Să luăm în considerare doar câteva abordări pentru rezolvarea acestor probleme. În primul rând, abordarea grafică este valabilă și în rezolvarea celor mai simple probleme de programare neliniară. Deci, dacă variabilele x1 și x2 sunt argumentele problemei, atunci, mai întâi, aria soluțiilor fezabile este construită pe planul acestor variabile și apoi, folosind nivelurile funcției obiectiv f(x1,x2 ), se determină punctul optim în zonă. În programarea neliniară, o abordare gradient este utilizată pentru a rezolva multe probleme. Există o serie de metode de gradient, a căror esență este găsirea rezultatului optim folosind gradientul funcției obiectiv - un vector care indică direcția creșterii maxime a obiectivului pentru punctul luat în considerare. În cazul general, procedura de căutare se efectuează într-un mod iterativ de la punctul selectat inițial până la punctele cu cel mai bun indicator. Să fie, de exemplu, . -
domeniul soluţiilor admisibile problema considerată, iar procesul iterativ al calculelor începe de la punct Mai mult, mai întâi, se face o tranziție de-a lungul gradientului funcției obiectiv și apoi o întoarcere în zonă. de-a lungul gradientului până la limita perturbată a regiunii O2 O3. 13.3 se arată că Ai cu indici impari aparțin zonei., iar punctele Ai cu indici pari nu. Pe măsură ce ne apropiem de punctul optim Q, direcțiile gradienților de lucru converg. Prin urmare, criteriul ideal pentru oprirea procesului va fi coliniaritatea gradientului țintă și a gradientului limită întreruptă. 67. Conceptul de programare parametrica si intreaga
. Enunț și model matematic al ZCLP. În problemele cu obiecte indivizibile, condițiile întregi sunt impuse variabilelor. Uneori, aceste condiții se aplică tuturor variabilelor, alteori unora dintre variabile. Luați în considerare o problemă cu numere întregi f=(n,j=1)∑CjXi max (n,j=1)∑AijXj=bi, i=1,m xi-întreg,j=1,n Acum, spre deosebire de problema generală de programare liniară, planul optim nu va fi neapărat la vârful poliedrului planului.Există următoarele metode pentru rezolvarea problemelor cu numere întregi: 1. Metode de tăiere 2.Combinatoriu 3.Metode aproximative.. Programarea parametrică este o secțiune de programare matematică dedicată studiului problemelor de optimizare în care condițiile de admisibilitate și funcția obiectiv depind de niște parametri determiniști.
Definiție. Programare liniară (LP) -știința metodelor de cercetare și găsirea valorilor extreme (maxime și minime) ale unei funcții liniare, asupra necunoscutelor cărora li se impun restricții liniare.
Această funcție liniară se numește ţintă, iar constrângerile care sunt scrise matematic sub formă de ecuații sau inegalități sunt numite sistem de restricții.
Definiție. Se numește expresia matematică a funcției obiectiv și a constrângerilor acesteia modelul matematic al problemei economice.
În general, modelul matematic al unei probleme de programare liniară (LP) este scris ca
cu restrictii:
Unde x j- necunoscut; aij, b i, cj sunt date constante.
Toate sau unele ecuații ale sistemului de constrângeri pot fi scrise ca inegalități.
Modelul matematic într-o notație mai scurtă are forma
cu restrictii:
Definiție. O soluție fezabilă (plan) a unei probleme de programare liniară este un vector = ( X 1 , X 2 ,..., x p), satisfacerea sistemului de restricţii.
Mulțimea soluțiilor admisibile formează regiunea soluțiilor admisibile (ODD).
Definiție. O soluție fezabilă pentru care funcția obiectiv atinge valoarea sa extremă se numește soluția optimă a problemei de programare liniară și se notează opt.
Soluție de bază admisibilă (X 1 , X 2 ,...,X r , 0, …, 0) este o soluție de referință, unde r- rangul sistemului de constrângeri.
Modelul matematic al problemei LP poate fi canonic și non-canonic.
7. Rezolvarea problemelor de programare liniară printr-o metodă grafică. Grafice ale funcțiilor de constrângere. Linii de nivel.
Metodă grafică pentru rezolvarea problemelor de programare liniară
Cea mai simplă și mai vizuală metodă de programare liniară este metoda grafică. Este folosit pentru rezolvarea problemelor LP cu două variabile date în formă necanonică și multe variabile în formă canonică, cu condiția ca acestea să nu conțină mai mult de două variabile libere.
Din punct de vedere geometric, într-o problemă de programare liniară, se caută un astfel de punct de colț sau un set de puncte dintr-un set admisibil de soluții, la care se ajunge la linia de nivel cel mai înalt (inferioară), situată mai departe (mai aproape) decât celelalte în direcția celei mai rapide creșteri.
Pentru a găsi valoarea extremă a funcției obiectiv în rezolvarea grafică a problemelor LP, se folosește vectorul L() la suprafață X 1 OH 2 , pe care o notăm . Acest vector arată direcția celei mai rapide schimbări în funcția obiectiv. Cu alte cuvinte, vectorul este normala liniei de nivel L()
Unde e 1 și e 2 - vectori unitari de-a lungul axelor BOU 1 și BOU 2 respectiv; astfel = (∂L/∂x 1 , ∂L/∂х 2 ).
Coordonatele vectoriale sunt coeficienții funcției obiectiv L(). Construcția liniei de nivel va fi luată în considerare în detaliu la rezolvarea problemelor practice.
Algoritm de rezolvare a problemelor
1. Găsim zona soluțiilor fezabile pentru sistemul de constrângeri ale problemei.
2. Construirea unui vector .
3. Desenați o linie de nivel L 0 , care este perpendiculară .
4. Mutăm linia de nivel în direcția vectorului pentru sarcini la maxim și în direcția opusă , pentru sarcini minime.
Linia de nivel este mutată până când are un singur punct comun cu zona soluțiilor fezabile. Acest punct, care determină soluția unică a problemei LP, va fi punctul extremum.
Dacă se dovedește că linia de nivel este paralelă cu una dintre laturile ODT, atunci în acest caz se atinge extrema în toate punctele laturii corespunzătoare, iar problema LP va avea un număr infinit de soluții. Se spune că o astfel de problemă LP are optim alternativ iar soluția sa este dată de formula:
Unde 0 ≤ t≤ 1, 1 și 2 - soluții optime în punctele de colț ale ODS.
O problemă LP poate fi de nerezolvat atunci când constrângerile care o definesc se dovedesc a fi contradictorii.
5.
Găsim coordonatele punctului extremum și valoarea funcției obiectiv în el.
Exemplul 3 Alegerea celei mai bune opțiuni de lansare a produsului
Compania produce 2 tipuri de inghetata: smantana si ciocolata. Pentru fabricarea înghețatei se folosesc două produse inițiale: lapte și umpluturi, ale căror costuri pentru 1 kg de înghețată și provizii zilnice sunt date în tabel.
Cercetările de piață au arătat că cererea zilnică de înghețată cu unt depășește cererea de înghețată de ciocolată, dar cu cel mult 100 kg.
În plus, s-a constatat că cererea de înghețată de ciocolată nu depășește 350 kg pe zi. Prețul cu amănuntul al 1 kg de înghețată cremoasă este de 16 ruble, ciocolată - 14 ruble.
Cât din fiecare tip de înghețată ar trebui să producă firma pentru a-și maximiza veniturile din vânzări?
Decizie. Denota: X 1 - volumul zilnic de producție de înghețată cremoasă, kg; X 2 - producție zilnică de înghețată de ciocolată, kg.
Să facem un model matematic al problemei.
Prețurile pentru înghețată sunt cunoscute: 16 ruble, respectiv 14 ruble, astfel încât funcția obiectiv va arăta astfel:
Stabiliți limite pentru laptele pentru înghețată. Consumul acestuia pentru inghetata cremoasa este de 0,8 kg, pentru inghetata de ciocolata - 0,5 kg. Stoc de lapte 400 kg. Prin urmare, prima inegalitate va arăta astfel:
0,8x 1 + 0,5x 2 ≤400 - prima inegalitate este o restricție. Restul inegalităților sunt construite într-un mod similar.
Rezultatul este un sistem de inegalități. care este aria de soluție a fiecărei inegalități. Acest lucru se poate face prin înlocuirea coordonatele punctului O(0:0) în fiecare dintre inegalități. Ca rezultat, obținem:
Figura OABDEF- domeniul soluţiilor admisibile. Construim vectorul (16; 14). linie de nivel L 0 este dat de ecuația 16x 1 +14x 2 =Const. Alegem orice număr, de exemplu numărul 0, apoi 16x 1 +14x 2 =0. În figură, pentru linia L 0 se alege un număr pozitiv, diferit de zero. Toate liniile de nivel sunt paralele între ele. Vectorul normal al liniei de nivel.
Deplasați linia de nivel în direcția vectorului. punct de ieșire L 0 din regiunea soluțiilor fezabile este punctul D, coordonatele sale sunt definite ca intersecția dreptelor date de ecuațiile:
Rezolvând sistemul, obținem coordonatele punctului D(312,5; 300), în care va exista o soluție optimă, i.e.
Astfel, compania trebuie să producă 312,5 kg de înghețată cu unt și 300 kg de înghețată de ciocolată pe zi, în timp ce veniturile din vânzări vor fi de 9.200 de ruble.
8. Reducerea unei probleme de programare liniară arbitrară la problema principală. Transformarea constrângerilor date de inegalități în ecuații corespunzătoare.
9.Metoda simplex. Caracteristicile și algoritmul metodei, aplicabilitatea acesteia.
Pentru a rezolva problema prin metoda simplex, este necesar:
1. Indicați o metodă pentru găsirea soluției de referință optime
2. Precizați metoda de trecere de la o soluție de referință la alta, pe care valoarea funcției obiectiv va fi mai apropiată de cea optimă, i.e. indica o modalitate de a îmbunătăți soluția de referință
3. Stabiliți criterii care vă permit să opriți în timp util enumerarea soluțiilor de referință asupra soluției optime sau să dați o concluzie despre absența unei soluții optime.
Algoritmul metodei simplex pentru rezolvarea problemelor de programare liniară
1. Aduceți problema la forma canonică
2. Găsiți o soluție de referință inițială cu „bază unitară” (dacă nu există o soluție de referință, atunci problema nu are o soluție, din cauza incompatibilității sistemului de constrângeri)
3. Calculați estimări ale expansiunilor vectoriale în funcție de baza soluției de referință și completați tabelul metodei simplex
4. Dacă este îndeplinit criteriul de unicitate a soluției optime, atunci soluția problemei se termină
5. Dacă este îndeplinită condiția existenței unei mulțimi de soluții optime, atunci prin enumerare simplă se găsesc toate soluțiile optime
10. Sarcina de transport. Definitie, tipuri, metode de gasire a solutiei initiale a problemei transportului.
Problema transportului este una dintre cele mai comune probleme de programare liniară. Scopul său este de a dezvolta cele mai raționale modalități și mijloace de transport de mărfuri, eliminând transporturile excesiv de lungi, care se apropie, repetate.
1. Găsirea soluției inițiale de referință;
2. Verificarea optimității acestei soluții;
3. Tranziția de la o soluție de bază la alta.
T10. Enunțul problemei de programare liniară
model matematic O problemă economică este un set de relații matematice care descriu procesul economic.
Pentru a compila un model matematic, este necesar:
1. selectați variabilele sarcinii;
2. să întocmească un sistem de restricții;
3. stabiliți funcția obiectiv.
Variabilele sarcinii se numesc mărimile x 1 , x 2 ,…, x n care caracterizează pe deplin procesul economic. Ele sunt de obicei scrise ca un vector X \u003d (x 1, x 2, ..., x n).
Sistem de constrângere a sarcinilor este un ansamblu de ecuații și inegalități care sunt satisfăcute de variabilele problemei și care decurg din resursele limitate și alte condiții economice, de exemplu, pozitivitatea variabilelor. În general, ele arată astfel:
Funcția obiectiv este numită funcția F(X) = f(x 1 , x 2 ,…, x n) a variabilelor sarcinii, care caracterizează calitatea sarcinii și a cărei extremă trebuie găsită.
Problema generală de programare matematică se formulează astfel: găsiți variabilele sarcinii x 1 , x 2 ,…, x n care furnizează extremul funcției obiectiv
F (X) \u003d f (x 1, x 2, ..., x n) ® max (min) (2)
și să satisfacă sistemul de constrângeri (1).
Dacă funcția obiectiv (2) și sistemul de constrângeri (1) sunt liniare, atunci problema programării matematice se numește problema de programare liniara (LPP).
Se apelează vectorul X (un set de variabile de sarcină). solutie acceptabila, sau planul PLP, dacă satisface sistemul de restricții (1). Se numește un plan X fezabil care oferă un extremum al funcției obiectiv soluție optimă ZLP.
2. Exemple de compilare a modelelor matematice ale problemelor economice
Studiul situațiilor specifice de producție duce la ZLP, care sunt interpretate ca probleme de utilizare optimă a resurselor limitate.
1.Problema planului optim de producție
Pentru producerea a două tipuri de produse T 1 și T 2 se folosesc trei tipuri de resurse S 1 , S 2 , S 3. Stocurile de resurse, numărul de unități de resurse cheltuite pentru fabricarea unei unități de producție, precum și profitul din vânzarea unei unități de producție sunt prezentate în tabel:
Este necesar să se găsească un astfel de plan pentru producția de produse în care profitul din vânzarea acestuia să fie maxim.
Decizie.
Să notăm x 1, x 2 - numărul de unități de producție, respectiv, T 1 și T 2, planificate pentru producție. Pentru fabricarea lor, vor fi necesare (x 1 + x 2) unități de resursă S 1, (x 1 + 4x 2) unități de resursă S 2, (x 1) unități de resursă S 3. Consumul de resurse S 1 , S 2 , S 3 nu trebuie să depășească rezervele acestora, respectiv 8, 20 și 5 unități.
Atunci modelul economico-matematic al problemei poate fi formulat astfel:
Găsiți un plan de producție X \u003d (x 1, x 2) care satisface sistemul de restricții: 
si starea
sub care funcţia capătă valoarea maximă.
Problema poate fi generalizată cu ușurință în cazul producerii a n tipuri de produse folosind m tipuri de resurse.
2.Problema dietei optime
Există două tipuri de alimente K 1 și K 2 care conțin nutrienți S 1 , S 2 și S 3 . Conținutul numărului de unități nutritive în 1 kg din fiecare tip de furaj, minimul necesar de nutrienți, precum și costul a 1 kg de furaj sunt prezentate în tabel:
Este necesar să se întocmească o rație zilnică care să aibă un cost minim, în care conținutul fiecărui tip de nutrient să nu fie mai mic decât limita stabilită.
Decizie.
Să notăm x 1, x 2 - cantitatea de furaje K 1 și K 2 incluse în dieta zilnică. Apoi, această dietă va include (3x 1 + x 2) unități de nutrient S 1, (x 1 + 2x 2) unități de substanță S 2, (x 1 + 6x 2) unități de nutrient S 3. Deoarece conținutul de nutrienți S 1 , S 2 și S 3 din dietă ar trebui să fie de 9, 8 și, respectiv, 12 unități, modelul economico-matematic al problemei poate fi formulat după cum urmează:
Compuneți o dietă zilnică X \u003d (x 1, x 2), satisfăcând sistemul de restricții:
si starea
sub care funcţia ia valoarea minimă.
Formulare de înregistrare PLP
În LLP, este necesar să se găsească extremul funcției obiective liniare:
cu restrictii:
și condiția de non-negativitate
unde a ij , b i , c j ( , ) sunt date constante.
Așa este scris ZLP-ul general formă. Dacă sistemul de constrângeri conține doar inegalități, atunci LLP este reprezentat în standard formă. Canonic (principal) forma notației ZLP este notația când sistemul de constrângeri conține doar egalități. Deci, LLP-urile de mai sus sunt scrise în formă standard.
Formele generale, standard și canonice ale LLP sunt echivalente în sensul că fiecare dintre ele, cu ajutorul unor transformări simple, poate fi rescrisă într-o formă diferită. Aceasta înseamnă că, dacă există o modalitate de a rezolva una dintre aceste probleme, atunci poate fi determinat planul optim pentru oricare dintre probleme.
Pentru a trece de la o formă de notație LLP la alta, trebuie să fii capabil să treci de la constrângeri de inegalitate la constrângeri de egalitate și invers.
O constrângere de inegalitate (£) poate fi convertită într-o constrângere de egalitate adăugând o variabilă suplimentară nenegativă în partea stângă, iar o constrângere de inegalitate (³) poate fi convertită într-o constrângere de egalitate prin scăderea unei variabile suplimentare nenegative din ea. partea stanga. Numărul de variabile suplimentare nenegative introduse este egal cu numărul de constrângeri de inegalitate transformate.
Introdus variabilele suplimentare au sens economic. Astfel, dacă constrângerile PLP inițial reflectă consumul și disponibilitatea resurselor, atunci valoarea variabilei suplimentare PLP în formă canonică este egală cu volumul resursei corespunzătoare neutilizate.
Exemplul 1. Scrieți în forma canonică ZLP:
cu restrictii:
Decizie.
Funcția obiectiv rămâne neschimbată:
Sistemul de inegalități se transformă într-un sistem de egalități:
La rezolvarea LLP printr-o metodă grafică, este necesară o tranziție de la forma canonică la forma standard.
Pentru a aduce LLP într-o formă standard, utilizați metoda Jordan–Gauss Solutii SLAU. Spre deosebire de metoda Gauss, în care matricea extinsă a sistemului este redusă la o formă de pas, în metoda Jordan-Gauss se formează o matrice de identitate ca parte a matricei extinse. Prin urmare, nu este necesară o mișcare inversă aici.
Pentru a converti LLP canonic original în LLP standard echivalent:
a) în matricea extinsă a sistemului de constrângeri se alege un element diferit de zero a qp. Acest element este numit permisiv, și q - i rând și p-a coloană numite enable row și enable column.
b) șirul de rezolvare este rescris fără modificare, iar toate elementele coloanei de rezolvare, cu excepția coloanei de rezolvare, sunt înlocuite cu zerouri. Elementele rămase ale matricei augmentate sunt determinate folosind „regula dreptunghiului”:
Se consideră patru elemente ale matricei extinse: elementul a ij de transformat, elementul de rezoluție a qp și elementele a i p și a qj . Pentru a găsi elementul a ij, din elementul a ij rezultă să se scadă produsul elementelor a i p și a qj situate la vârfuri opuse ale dreptunghiului, împărțit la elementul de rezoluție a qp:
c) necunoscutele admise sunt excluse simultan din funcţia obiectiv. Pentru a face acest lucru, coeficienții funcției obiectiv sunt scriși în matricea extinsă din ultimul rând. Calculele iau în considerare faptul că elementul de activare din ultima linie nu poate fi selectat.
Exemplul 2. Modificare la forma standard:
Decizie.
Folosind metoda Jordan-Gauss, aducem sistemul de ecuații de constrângere LLP la un sistem echivalent de inegalități. Să alegem al treilea element din primul rând ca element de rezolvare:
Numărul -9 obținut în ultima coloană a ultimului rând trebuie scris în funcția obiectiv cu semnul opus. Ca rezultat al transformărilor, LLP ia forma:
pentru că variabilele x 2 și x 3 sunt nenegative, apoi eliminându-le, putem scrie ZLP într-o formă simetrică:
În forma canonică a LLP, funcția obiectiv poate fi atât minimizată, cât și maximizată. A trece de la găsirea maximului la găsirea minimului sau invers, este suficient să schimbați semnele coeficienților funcției obiectiv: F 1 = - F. Problema rezultată și LLP inițial au aceeași soluție optimă, iar valorile funcțiilor obiectiv de pe această soluție diferă numai în semn.
Proprietăți ZLP
1. Mulțimea tuturor soluțiilor admisibile ale sistemului de constrângeri ale unei probleme de programare liniară este convexă.
Setul de puncte este numit convex, dacă conține întregul segment care leagă oricare două puncte din această mulțime.
Conform acestei definiții, poligonul din fig. 1a este o mulțime convexă, în timp ce poligonul din fig. 1b nu este, deoarece segmentul MN dintre cele două puncte ale sale M și N nu aparține complet acestui poligon.
Mulțimile convexe pot fi nu numai poligoane. Exemple de mulțimi convexe sunt cerc, sector, segment, cub, piramidă etc.
2. Dacă LLP are o soluție optimă, atunci funcția liniară ia valoarea maximă (minimă) la unul dintre punctele de colț ale poliedrului de decizie. Dacă o funcție liniară ia o valoare maximă (minimă) la mai mult de un punct de colț, atunci o ia în orice punct care este o combinație liniară convexă a acestor puncte.
Punctul X este numit combinație liniară convexă punctele X 1 , X 2 ,…, X n dacă sunt îndeplinite următoarele condiții:
X \u003d α 1 X 1 + α 2 X 2 + ... + α n X n,
αj ≥ 0, Σαj = 1.
Este evident că în cazul special pentru n = 2 o combinație liniară convexă a două puncte este un segment care le leagă.
3. Fiecărei soluții de bază admisibile a sistemului de constrângeri LLP canonic îi corespunde un punct de colț al poliedrului de soluție și invers, fiecărui punct de colț al poliedrului de soluție îi corespunde o soluție de bază admisibilă.
Din ultimele două proprietăți rezultă că, dacă un LLP are o soluție optimă, atunci coincide cu cel puțin una dintre soluțiile sale de bază admisibile.
Astfel, extremul funcției liniare LLP trebuie căutat între un număr finit de soluții de bază admisibile.
Cursul 2
LA formă canonică
soluție admisibilă a PLP(plan acceptabil).
soluția optimă a LLP.
Nevoie
Exemplu. 
Să scriem problema în formă canonică
Situații speciale ale soluției grafice a ZLP
Cu excepția cazului în care sarcina este singura solutie optima pentru și , poate fi situatii speciale:
1. sarcina are un număr infinit de soluții optime – se atinge extremul funcției pe segment ( optim alternativ)- Figura 2;
2. sarcină nesolubil din cauza caracterului nelimitat al ODR, sau - Figura 3;
3. ODR - un singur punct Ah, atunci;
4. sarcina nesolubil dacă ODR are o zonă goală.
DAR
Figura 2 Figura 3
Dacă linia de nivel este paralelă cu partea zonei soluțiilor fezabile, atunci extremul este atins în toate punctele laterale. Problema are un număr infinit de soluții optime - optim alternativ . Soluția optimă se găsește prin formulă
unde este parametrul. Pentru orice valoare de la 0 la 1, puteți obține toate punctele segmentului, pentru fiecare dintre acestea funcția ia aceeași valoare. De aici și numele - optim alternativ.
Exemplu. Rezolvați grafic problema de programare liniară ( optim alternativ):
Întrebări pentru autocontrol
1. Notați problema de programare liniară în formă generală.
2. Scrieți problema de programare liniară în forme canonice și standard.
3. Ce transformări pot fi folosite pentru a trece de la forma generală sau standard a unei probleme de programare liniară la cea canonică?
4. Dați o definiție a soluțiilor fezabile și optime ale problemei de programare liniară.
5. Care dintre soluții este „cea mai bună” pentru problema minimizării funcției dacă 
?
6. Care dintre soluții este „cea mai bună” pentru problema maximizării funcției dacă ?
7. Notați forma standard a modelului matematic al unei probleme de programare liniară cu două variabile.
8. Cum se construiește un semiplan dat de o inegalitate liniară cu două variabile 
?
9. Cum se numește soluția unui sistem de inegalități liniare cu două variabile? Construiți pe plan domeniul soluțiilor fezabile ale unui astfel de sistem de inegalități liniare, care:
1) are o soluție unică;
2) are un set infinit de soluții;
3) nu are soluție.
10. Scrieți pentru o funcție liniară 
gradient vectorial, denumește tipul de linii de nivel. Cum sunt situate liniile de gradient și de nivel una față de alta?
11. Formulați un algoritm pentru o metodă grafică de rezolvare a unui LLP standard cu două variabile.
12. Cum să găsiți coordonatele și valorile soluției, ?
13. Construiți aria soluțiilor fezabile, linii de gradient și nivel, pentru probleme de programare liniară în care:
1) se ajunge într-un singur punct, iar - pe segmentul ODR;
2) se ajunge într-un singur punct al ODS și .
14. Oferiți o ilustrare geometrică a LLP dacă:
1) are soluții optime unice pentru și ;
2) are un set de soluții optime pentru .
Cursul 2
metoda grafica de gasire a solutiei optime
1. Forme ale modelelor matematice liniare și transformarea lor
2. Metodă grafică pentru rezolvarea unei probleme de programare liniară
3. SITUAȚII SPECIALE ALE SOLUȚIEI GRAFICE A LLP
4. Rezolvarea grafică a problemelor economice de programare liniară
Forme ale modelelor matematice liniare și transformarea lor
Un model matematic al unei probleme de programare liniară (LPP) poate fi scris într-una din trei forme.
LA forma generală a modelului matematic se cere găsirea maximului sau minimului funcției obiectiv; sistemul de constrângeri conține inegalități și ecuații; nu toate variabilele pot fi nenegative.
LA formă canonică modelul matematic trebuie să găsească maximul funcției obiectiv; sistemul de constrângeri este format numai din ecuații; toate variabilele sunt nenegative.
În forma standard a unui model matematic, se cere să se găsească maximul sau minimul unei funcții; toate constrângerile sunt inegalități; toate variabilele sunt nenegative.
Se numește soluția sistemului de constrângeri care satisface condițiile de nenegativitate a variabilelor soluție admisibilă a PLP(plan acceptabil).
Setul de soluții fezabile se numește zona soluțiilor fezabile ale LLP.
Se numește o soluție fezabilă, în care funcția obiectiv atinge o valoare extremă soluția optimă a LLP.
Cele trei forme ale LLP sunt echivalente în sensul că fiecare dintre ele poate fi redusă la o formă diferită cu ajutorul transformărilor matematice.
Nevoie trecerea de la o formă de model matematic la alta asociate cu metode de rezolvare a problemelor: de exemplu, metoda simplex, utilizată pe scară largă în programarea liniară, se aplică unei probleme scrise în formă canonică, iar metoda grafică se aplică formei standard a unui model matematic.
Trecerea la notația canonică ZLP.
Exemplu.
Să scriem problema în formă canonică, introducând o variabilă suplimentară (balanță) cu semnul „+” în partea stângă a primei inegalități a sistemului de constrângeri și o variabilă suplimentară cu semnul „minus” în partea stângă a celei de-a doua inegalități.
Semnificația economică a diferitelor variabile suplimentare poate să nu fie aceeași: depinde de semnificația economică a restricțiilor în care sunt incluse aceste variabile.
Deci, în problema utilizării materiilor prime, ele arată restul materiilor prime, iar în problema alegerii tehnologiilor optime, arată timpul nefolosit al întreprinderii folosind o anumită tehnologie; în problema tăierii - eliberarea semifabricatelor de o lungime dată peste plan etc.
Baza pentru rezolvarea problemelor economice sunt modelele matematice.
Elaborarea unui model matematic include:model matematic problema este un set de relații matematice care descriu esența problemei.
- selectarea variabilei sarcinii
- elaborarea unui sistem de restricţii
- alegerea funcției obiective
Variabilele sarcinii se numesc marimi X1, X2, Xn, care caracterizeaza pe deplin procesul economic. De obicei ele sunt scrise ca un vector: X=(X 1 , X 2 ,...,X n).
Sistemul de restricții sarcinile sunt un set de ecuații și inegalități care descriu resursele limitate din problema luată în considerare.
funcția țintă sarcina se numește o funcție a variabilelor sarcinii care caracterizează calitatea sarcinii și al cărui extremum trebuie găsit.
În general, o problemă de programare liniară poate fi scrisă după cum urmează:
Această intrare înseamnă următoarele: găsiți extremul funcției obiectiv (1) și variabilele corespunzătoare X=(X 1 , X 2 ,...,X n) cu condiția ca aceste variabile să satisfacă sistemul de constrângeri (2) și non -condiții de negativitate (3) .
Soluție acceptabilă(planul) unei probleme de programare liniară este orice vector n-dimensional X=(X 1 , X 2 ,...,X n) care satisface sistemul de constrângeri și condiții de nenegativitate.
Se formează setul de soluții (planuri) fezabile ale problemei gama de solutii fezabile(ODR).
Soluția optimă(planul) unei probleme de programare liniară este o astfel de soluție (plan) fezabilă a problemei, în care funcția obiectiv atinge un extremum.
Un exemplu de compilare a unui model matematic
Sarcina utilizării resurselor (materii prime)
Condiție: Pentru fabricarea a n tipuri de produse se folosesc m tipuri de resurse. Realizați un model matematic.
Cunoscut:
- b i (i = 1,2,3,...,m) sunt rezervele fiecărui i-lea tip de resursă;
- a ij (i = 1,2,3,...,m; j=1,2,3,...,n) sunt costurile fiecărui i-a tip de resursă pentru producerea unui volum unitar de al j-lea tip de produs;
- c j (j = 1,2,3,...,n) este profitul din vânzarea unui volum unitar de al j-lea tip de produs.
Este necesar să se întocmească un plan de producție de produse care să ofere profit maxim cu restricții date asupra resurselor (materii prime).
Decizie:
Introducem un vector de variabile X=(X 1 , X 2 ,...,X n), unde x j (j = 1,2,...,n) este volumul de productie al j-lea tip de produs.
Costurile celui de-al i-lea tip de resursă pentru producerea unui volum dat x j de produse sunt egale cu a ij x j , prin urmare, restricția privind utilizarea resurselor pentru producerea tuturor tipurilor de produse are forma:
Profitul din vânzarea celui de-al-lea tip de produs este egal cu c j x j , deci funcția obiectiv este egală cu:
Răspuns- Modelul matematic arată astfel:
Forma canonică a unei probleme de programare liniară
În cazul general, o problemă de programare liniară este scrisă în așa fel încât atât ecuațiile, cât și inegalitățile să fie constrângeri, iar variabilele pot fi fie nenegative, fie în schimbare arbitrară.
În cazul în care toate constrângerile sunt ecuații și toate variabilele satisfac condiția de non-negativitate, problema de programare liniară se numește canonic.
Poate fi reprezentat în notație de coordonate, vector și matrice.
Problema de programare liniară canonică în notație de coordonate are forma:
Problema de programare liniară canonică în notație matriceală are forma:
- A este matricea coeficienților sistemului de ecuații
- X este o matrice de coloană a variabilelor sarcinii
- Ao este coloana-matrice a părților drepte ale sistemului de constrângeri
Adesea se folosesc probleme de programare liniara, numite simetrice, care in notatie matriceala au forma:
Reducerea unei probleme generale de programare liniară la formă canonică
În majoritatea metodelor de rezolvare a problemelor de programare liniară, se presupune că sistemul de constrângeri este format din ecuații și condiții naturale pentru non-negativitatea variabilelor. Cu toate acestea, la compilarea modelelor de probleme economice, constrângerile se formează în principal sub forma unui sistem de inegalități, deci este necesar să se poată trece de la un sistem de inegalități la un sistem de ecuații.
Acest lucru se poate face astfel:Luați o inegalitate liniară a 1 x 1 +a 2 x 2 +...+a n x n ≤b și adăugați în partea stângă o valoare x n+1 astfel încât inegalitatea să devină egalitatea a 1 x 1 +a 2 x 2 + ...+a n x n +x n+1 =b. Mai mult, această valoare x n+1 este nenegativă.
Să luăm în considerare totul cu un exemplu.
Exemplul 26.1Reduceți problema de programare liniară la forma canonică:
Decizie:
Să trecem la problema găsirii maximului funcției obiectiv.
Pentru a face acest lucru, schimbăm semnele coeficienților funcției obiectiv.
Pentru a converti a doua și a treia inegalități ale sistemului de constrângeri în ecuații, introducem variabile suplimentare nenegative x 4 x 5 (această operație este marcată cu litera D pe modelul matematic).
Variabila x 4 este introdusă în partea stângă a celei de-a doua inegalități cu semnul „+”, deoarece inegalitatea are forma „≤”.
Variabila x 5 este introdusă în partea stângă a celei de-a treia inegalități cu semnul „-”, deoarece inegalitatea are forma „≥”.
Variabilele x 4 x 5 sunt introduse în funcția obiectiv cu un coeficient. egal cu zero.
Scriem problema în formă canonică.
Se încarcă...