Rezolvarea problemelor MOP (metode de optimizare). Baza metodologică pentru elaborarea deciziilor de management Soluția se numește optimă

Programare liniară este o ramură a matematicii care studiază metode de găsire a minimului sau maximului unei funcții liniare a unui număr finit de variabile, cu condiția ca variabilele să satisfacă un număr finit de constrângeri sub formă de ecuații liniare sau inegalități liniare.

Astfel, sarcina generală programare liniară(ZLP) poate fi formulat după cum urmează.

Găsiți valori ale variabilelor reale pentru care funcţie obiectivă

ia o valoare minimă pe mulţimea de puncte ale căror coordonate satisfac sistem de restricții

După cum se știe, o colecție ordonată de valori n variabilele , , … este reprezentată de un punct din spațiul n-dimensional. În cele ce urmează vom nota acest punct X=( , , … ).

Sub formă de matrice, problema de programare liniară poate fi formulată după cum urmează:

, O- matricea dimensiunilor,

Punct X=( , , … ), care îndeplinește toate condițiile, este numit punct valabil . Se numește setul tuturor punctelor admisibile zonă valabilă .

Soluție optimă (plan optim) o problemă de programare liniară se numește soluție X=( , , … ), aparținând regiunii admisibile și pentru care funcția liniară Q ia valoarea optimă (maximă sau minimă).

Teorema. Setul tuturor soluțiilor fezabile ale sistemului de constrângeri ale unei probleme de programare liniară este convex.

Setul de puncte este numit convex , dacă, împreună cu oricare dintre punctele sale, conține combinația lor liniară convexă arbitrară.

Punct X numit combinație liniară convexă puncte dacă sunt îndeplinite condițiile

Setul tuturor soluțiilor fezabile la o problemă de programare liniară este o regiune poliedrică convexă, pe care o vom numi de acum înainte poliedru de soluții .

Teorema. Dacă ZLP are o soluție optimă, atunci funcția obiectiv ia valoarea maximă (minimă) la unul dintre vârfurile poliedrului soluție. Dacă funcția obiectiv ia o valoare maximă (minimă) în mai mult de un punct, atunci ia această valoare în orice punct care este o combinație liniară convexă a acestor puncte.

Printre numeroasele soluții ale sistemului m ecuații liniare care descriu poliedrul soluțiilor, se disting așa-numitele soluții de bază.

Soluția de bază a sistemului m ecuațiile liniare cu n variabile este o soluție în care toate n-m variabilele non-core sunt zero. În problemele de programare liniară se numesc astfel de soluții soluţii de bază admisibile (planuri de referinţă).

Teorema. Fiecărei soluții de bază admisibile unei probleme de programare liniară îi corespunde un vârf al poliedrului soluție și invers, fiecărui vârf al poliedrului soluției îi corespunde o soluție de bază admisibilă.

Din teoremele de mai sus rezultă un corolar important:

Dacă o problemă de programare liniară are o soluție optimă, atunci aceasta coincide cu cel puțin una dintre soluțiile sale de bază fezabile.

În consecință, optimul funcției liniare a scopului unei probleme de programare liniară trebuie căutat între numărul finit al soluțiilor sale de bază fezabile.

Baza pentru rezolvarea problemelor economice sunt modelele matematice.

Model matematic problema este un set de relații matematice care descriu esența problemei.

• selectarea variabilelor problemei
• elaborarea unui sistem de restricţii
• alegerea funcției obiective

Variabile de sarcină se numesc marimile X1, X2, Xn, care caracterizeaza complet procesul economic. Ele sunt de obicei scrise ca un vector: X=(X 1, X 2,...,X n).

Sistemul de restricții problemele sunt un set de ecuații și inegalități care descriu resursele limitate din problema luată în considerare.

Funcția obiectivă sarcinile sunt numite o funcție a variabilelor sarcinii care caracterizează calitatea sarcinii și al căror extremum trebuie găsit.

ÎN caz general Problema 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 restricții (2) și condiţii de non-negativitate (3) .

Soluție valabilă(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 non-negativitate.

Se formează setul de soluții (planuri) fezabile ale problemei regiune a soluțiilor fezabile(ODR).

Soluția optimă(planul) unei probleme de programare liniară este o astfel de soluție (plan) admisibilă a problemei în care funcția obiectiv atinge un extremum.

Exemplu de compilare a unui model matematic

Problema utilizării resurselor (materii prime)

Stare: Pentru a produce n tipuri de produse se folosesc m tipuri de resurse. Creați un model matematic.

Cunoscut:

• b i (i = 1,2,3,...,m) — rezerve ale fiecărui i-lea tip de resursă;
• a ij (i = 1,2,3,...,m; j=1,2,3,...,n) - costurile fiecărui i-a tip de resursă pentru producerea unei unități de volum al j-lea tip de produs;
• c j (j = 1,2,3,...,n) - profit din vânzarea unei unități de volum din al-lea tip de produs.

Este necesar să se întocmească un plan de producție care să asigure un profit maxim în limitele date privind resursele (materii prime).

Soluţie:

Să introducem un vector de variabile X=(X 1, X 2,...,X n), unde x j (j = 1,2,...,n) este volumul de producție 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 j-lea tip de produs este egal cu c j x j, deci funcția obiectiv este egală cu:

Răspuns- Model matematic are forma:

Forma canonică a unei probleme de programare liniară

În cazul general, o problemă de programare liniară este scrisă în așa fel încât constrângerile să fie atât ecuații, cât și inegalități, iar variabilele pot fi fie nenegative, fie variabile în mod 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 — matrice-coloană a variabilelor sarcinii
• Ао — matrice-coloană a părților drepte ale sistemului de restricții

Sunt adesea folosite probleme de programare liniară, numite simetrice, care în notația matriceală 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.

Să luăm inegalitatea liniară a 1 x 1 +a 2 x 2 +...+a n x n ≤b și să adăugăm în partea stângă o anumită valoare x n+1 astfel încât inegalitatea să se transforme în 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ă privim totul folosind un exemplu.

Aduceți problema de programare liniară la forma canonică:

Soluţie:
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 transforma a doua și a treia inegalități ale sistemului de constrângeri în ecuații, introducem variabile suplimentare nenegative x 4 x 5 (în modelul matematic această operație este marcată cu litera D).
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ă.

Cercetare operațională este o disciplină matematică complexă care se ocupă cu construirea, analiza și aplicarea modelelor matematice pentru luarea deciziilor optime în timpul operațiilor.

Obiectul cercetării operaționale- sisteme de management organizațional sau organizații care constau dintr-un număr mare de unități care interacționează care nu sunt întotdeauna consecvente între ele și pot fi opuse.

Scopul cercetării operaționale- justificarea cantitativă a deciziilor luate cu privire la managementul organizaţiilor

Operațiunea- un sistem de acțiuni controlate, unite printr-un singur plan și care vizează atingerea unui scop specific.

Setul de parametri de control (variabile) în timpul unei operații este apelat decizie. Soluția se numește acceptabil , dacă îndeplinește un set de anumite condiții. Soluția se numește optim

, dacă este acceptabil și, după anumite criterii, preferabil altora, sau cel puțin nu mai rău. Semn de preferință

numit criteriul de optimitate. Criteriul de optimizare

include o funcție obiectiv, o direcție de optimizare sau un set de funcții obiectiv și direcții de optimizare corespunzătoare. Funcția obiectivă

este un indicator cantitativ al preferinței sau eficacității soluțiilor. Direcția de optimizare

- acesta este maximul (minimul) dacă valoarea cea mai mare (cea mai mică) a funcției obiectiv este cea mai preferată.

De exemplu, criteriul poate fi maximizarea profiturilor sau minimizarea costurilor.

Modelul matematic al problemei IO include:

1) descrierea variabilelor care trebuie găsite;

2) descrierea criteriilor de optimitate;– justifica cantitativ si calitativ decizia luata. Decizia finală este luată de persoana responsabilă sau grupul de persoane numit decident.

Un vector care satisface un sistem de constrângeri se numește solutie acceptabilasau plan ZLP. Setul tuturor planurilor este numit zonă valabilă sauzona de soluții fezabile. Se numește planul care oferă maximul (minimul) funcției obiectivplan optim sausoluție optimă pentru ZLP. Astfel,rezolva PIL – înseamnă găsirea planului optim.

Este foarte simplu să aduci ZLP-ul general la cel principal, folosind următoarele reguli evidente.

Minimizarea funcției obiective f este echivalent cu maximizarea funcției g = – f.

O constrângere de inegalitate este echivalentă cu o ecuație cu condiția ca variabila suplimentară.

Dacă pentru o variabilă x j nu se impune conditia de non-negativitate, apoi se face o schimbare de variabila.

Linie de nivel funcții f, adică linia de-a lungul căreia această funcție ia aceeași valoare fixă Cu, adică f(x 1 , x 2)= c

Setul de puncte este numit convex, dacă acesta, împreună cu oricare dintre punctele sale, conține întregul segment care leagă aceste puncte.

În cazul a două variabile, mulțimea soluțiilor unei inegalități liniare (ecuație) este un semiplan (linie dreaptă).

Intersecția acestor semiplane (și drepte, dacă sistemul de constrângeri are ecuații) reprezintă regiunea fezabilă. Dacă nu este gol, atunci este o mulțime convexă și este numită.

poligon soluție În cazul a trei variabile, regiunea admisibilă a ZLP este intersecția semi-spațiilor și, eventual, a planurilor și se numește

poliedru de soluțiiSistemul de ecuații liniare se numește, sistem cu bază dacă fiecare ecuație conține o necunoscută cu coeficient egal cu 1, care este absentă în celelalte ecuații ale sistemului. Aceste necunoscute sunt numite, de bază – odihnă.

gratuit Vom numi sistemul de ecuații liniare, canonicdacă este un sistem cu o bază și atât b i ≥ 0. Soluția de bază în acest caz se dovedește a fi un plan, deoarece componentele sale sunt nenegative. Să-l sunăm de bază (sau) plan de sprijin

sistem canonic. Vom numi sistemul de ecuații liniare Îi vom numi OZLP

(KZLP), dacă sistemul de ecuații liniare al acestei probleme este canonic, iar funcția obiectiv este exprimată numai în termeni de necunoscute libere. Dacă în tabelul simplex există cel puțin un element pozitiv printre coeficienți pentru orice necunoscut liber, atunci este posibilă o tranziție la o nouă problemă canonică, echivalentă cu cea originală, în care necunoscuta liberă specificată se dovedește a fi de bază (în în acest caz, una dintre necunoscutele de bază devine liberă) .

Teorema 2. (cu privire la îmbunătățirea liniei de bază) j , iar în coloana x j Dacă există cel puțin un element pozitiv, iar relația cheie este >0, atunci este posibilă o tranziție la o problemă canonică echivalentă cu un design de bază nu mai rău.

Teorema 3. (condiție suficientă pentru optimitate). 0 Dacă toate elementele rândului index al tabelului simplex al unei probleme de maximizare sunt nenegative, atunci proiectul de bază al acestei probleme este optim și cu

există un maxim al funcţiei obiectiv pe setul de planuri probleme.. Teorema 4(cazul funcției obiective nemărginite) j . j Dacă rândul index al tabelului simplex al unei probleme de maximizare conține un element negativ cu

, iar în coloana necunoscută x

toate elementele sunt nepozitive, atunci pe setul de planuri de probleme funcția obiectiv nu este mărginită de sus.

Metoda simplex:

Scriem acest KZLP în tabelul simplex original.

Dacă toate elementele rândului index al tabelului simplex sunt nenegative, atunci planul de bază al problemei este optim (Teorema 3).

Dacă rândul index conține un element negativ peste care nu există niciun element pozitiv în tabel, atunci funcția obiectiv nu este mărginită de sus pe mulțimea de planuri și problema nu are soluții (Teorema 4).

Dacă există cel puțin un element pozitiv în tabel deasupra fiecărui element negativ al rândului index, atunci ar trebui să treceți la un nou tabel simplex pentru care planul de bază nu este mai rău decât cel anterior (Teorema 2). În acest scop (vezi demonstrația teoremei 1) dacă este un sistem cu o bază și atât b selectați o coloană cheie în tabel, la baza căreia se află orice element negativ al rândului index;

selectați relația cheie (cea mai mică dintre relații

Când luăm în considerare tabelul simplex rezultat, unul dintre cele trei cazuri descrise în paragrafe se va prezenta cu siguranță. 2, 3, 4. Dacă la paragrafele apar situații. 2 sau 3, atunci procesul de rezolvare a problemei se termină, dar dacă apare situația de la pasul 4, atunci procesul continuă.

Dacă luăm în considerare faptul că numărul de planuri de bază diferite este finit, atunci sunt posibile două cazuri:

după un număr finit de pași problema va fi rezolvată (vor apărea situațiile 2 sau 3);

pornind de la un anumit pas apare buclă(repetarea periodică a tabelelor simplex și a planurilor de bază).

Aceste sarcini sunt numite probleme duale simetrice.

Să remarcăm următoarele caracteristici care conectează aceste sarcini:

Una dintre probleme este o problemă de maximizare, iar cealaltă este o problemă de minimizare.

În problema de maximizare, toate inegalitățile sunt ≤, iar în problema de minimizare, toate inegalitățile sunt ≥.

Numărul de necunoscute ale unei probleme este egal cu numărul de inegalități ale celeilalte probleme.

Matricele de coeficienți pentru necunoscutele în inegalitățile ambelor probleme sunt transpuse reciproc.

Termenii liberi ai inegalităților uneia dintre probleme sunt egali cu coeficienții necunoscutelor corespunzătoare în exprimarea funcției obiective a celeilalte probleme.

Algoritm pentru construirea unei probleme duale.

1. Aduceți toate inegalitățile sistemului de constrângeri ale problemei inițiale într-un singur sens - la formă canonică.

2. Creați o matrice extinsă a sistemului A, care include coloana b i și coeficienții funcției obiectiv F.

3. Aflați matricea transpusă A T.

4. Notează problema duală. Teorema 5.

f(x) ≤ g(Valoarea funcției obiective a problemei de maximizare pentru oricare dintre planurile sale nu depășește valoarea funcției obiective a problemei sale de minimizare duală pentru oricare dintre planurile sale, și anume, următoarea inegalitate este valabilă:),

y numit.

inegalitatea de bază a dualității (Teorema 6.condiție suficientă pentru optimitate

). (Dacă pentru unele planuri de probleme duale valorile funcțiilor obiective sunt egale, atunci aceste planuri sunt optime.Teorema 7. teorema fundamentală a dualității).

Dacă un ZLP are un optim finit, atunci dualul său are și un optim finit și (valori optimefuncţiile ţintă coincid. Dacă funcția obiectivă a uneia dintre problemele duale nu este limitată, atunci condițiile celeilalte probleme sunt contradictorii.

Teorema 8.

Componentele soluției optime la ZLP dual sunt egale cu elementele corespunzătoare ale rândului index al tabelului simplex optim al problemei directe, corespunzătoare variabilelor suplimentare.

Teorema 11.(criteriul pentru optimitatea unui plan de probleme de transport). Pentru ca planul de transport) să fie optim, este necesar și suficient să existe numere () și () care să îndeplinească următoarele condiții:

a) pentru toate celulele de bază ale planului (>0);

b) pentru toate celulele libere (=0).

Metoda potențială

Pasul 1. Verificați dacă această sarcină de transport este închisă. Dacă da, atunci treceți la pasul al doilea. Dacă nu, atunci reduceți-o la o problemă închisă prin introducerea fie a unui furnizor fictiv, fie a unui consumator fictiv.

Pasul 2. Găsiți soluția de referință inițială (planul de referință inițial) a problemei de transport închis.

Pasul 3. Verificați soluția de asistență rezultată pentru optimitate:

calculați potențialul furnizorului pentru acesta u i si consumatorii v j

pentru toate celulele libere ( b, j) calculează estimări;

dacă toate estimările sunt nepozitive (), atunci soluția problemei este finalizată: planul de referință inițial este optim. Dacă printre evaluări există cel puțin una pozitivă, atunci trecem la pasul al patrulea.

Pasul 4. Selectați celula ( b * ,j * ) cu cea mai mare estimare pozitivă și pentru aceasta construiți un ciclu închis de redistribuire a mărfurilor. Ciclul începe și se termină în celula selectată. b * , j * Obținem o nouă soluție de suport în care celula (

) va fi ocupat. Să revenim la al treilea pas.

După un număr finit de pași, se va obține o soluție optimă, adică un plan optim pentru transportul produselor de la furnizori la consumatori. Un punct se numește punct maxim local

, dacă există o vecinătate a acestui punct astfel încât

Conditii necesare optimitatii x * Pentru ca o funcție a unei variabile să aibă într-un punct

extremul local, este necesar ca derivata funcției în acest punct să fie egală cu zero,

Pentru ca o funcție să aibă un extremum local într-un punct, este necesar ca toate derivatele sale parțiale în acest punct să dispară x * Dacă la punct x * prima derivată a funcției este egală cu zero, iar a doua derivată >0, apoi funcția din punct<0 то функция в точке x * are un minim local dacă 2 produse,

are un maxim local. Teorema 4. x * Dacă o funcţie a unei variabile are într-un punct n - derivate până la (

1) ordinul este egal cu zero, iar derivata ordinului n nu este egală cu 0, atunci, n Dacă x * chiar, apoi punct

este un punct minim dacă,fn(x)>0<0.

punct maxim dacă fn(x) n Dacă x * ciudat, apoi punct

– punctul de inflexiune. matrice de formă pătratică .

Forma pătratică (5) se numește definit pozitiv, dacă pentru Q(X) >0 și definit negativ, dacă pentru.Q(X)<0

Matricea simetrică O numit definit pozitiv, dacă forma pătratică (5) construită din aceasta este definită pozitiv.

Se numește o matrice simetrică definit negativ, dacă forma pătratică (6) construită din aceasta este definită negativă.

Criteriul Sylvester: o matrice este definită pozitivă dacă toate unghiulare minore sunt mai mari decât zero.

O matrice este negativă definită dacă alternează semnele minorilor de colț.

Pentru ca o matrice să fie definită pozitivă, toate valorile sale proprii trebuie să fie mai mari decât zero.

Valori proprii– rădăcinile polinomului.

O condiție suficientă pentru optimitate este dată de următoarea teoremă.

Teorema 5. Dacă într-un punct staționar matricea Hessian este definită pozitiv, atunci acest punct este un punct minim local, dacă matricea Hessian este definită negativ, atunci acest punct este un punct maxim local.

Conflict este o contradicție cauzată de interesele opuse ale părților.

Situație conflictuală- o situație în care părțile ale căror interese sunt total sau parțial opuse.

joc - este un conflict real sau formal în care există cel puțin doi participanți, fiecare dintre ei se străduiește să-și atingă propriile obiective

Regulile jocului numiți acțiunile permise ale fiecărui jucător care vizează atingerea unui anumit scop.

Prin plata se numește evaluarea cantitativă a rezultatelor jocului.

Joc de dublu– un joc la care participă doar două părți (doi jucători).

Joc cu sumă zero sau antagonist - un joc de dublu în care suma plății este zero, adică dacă pierderea unui jucător este egală cu câștigul celuilalt.

Se numește alegerea și implementarea uneia dintre acțiunile prevăzute de reguli rândul jucătorului. Mișcările pot fi personale și aleatorii.

Mișcare personală este o alegere conștientă de către un jucător a uneia dintre acțiunile posibile (de exemplu, o mutare într-un joc de șah).

Mișcare aleatorie este o acțiune aleasă aleatoriu (de exemplu, alegerea unei cărți dintr-un pachet amestecat).

Strategie jucător - aceasta este alegerea fără ambiguitate a jucătorului în fiecare dintre situațiile posibile în care acest jucător trebuie să facă o mișcare personală.

Strategia optimă- aceasta este strategia unui jucător care, atunci când jocul este repetat de mai multe ori, îi oferă acestuia câștigul mediu maxim posibil sau pierderea medie minimă posibilă.

Matricea de plată– matricea rezultată A sau, cu alte cuvinte, matricea jocului s.

Joc finit al dimensiunilor(m  n) este un joc definit de o matrice A de dimensiune (m  n).

Maximin sau cel mai mic preț al jocului să numim numărul alpa = max(i)(min aij)(j)

și strategia corespunzătoare (șir) maximin.

Minimax sau prețul de top al jocului să numim numărul Beta = min(j)(max aij)i

și strategia corespunzătoare (coloana) minimax.

Prețul inferior al jocului nu depășește întotdeauna prețul superior al jocului.

Joc cu un vârf de șa numit jocul pentru care. Alp = beta

Cu prețul jocului se numeste cantitatea v daca.v = alp = beta

Strategie mixtă jucătorul este un vector, fiecare dintre componentele căruia arată frecvența relativă a utilizării de către jucător a strategiei pure corespunzătoare.

Teorema 2 .

Teorema principală a teoriei jocurilor matriceale.

Fiecare joc cu matrice cu sumă zero are o soluție în strategii mixte.3

T

Dacă unul dintre jucători folosește o strategie mixtă optimă, atunci câștigul său este egal cu costul jocului  indiferent de frecvența cu care al doilea jucător își folosește strategiile (inclusiv strategiile pure).

jocul cu natura - un joc în care nu avem informații despre comportamentul parteneruluiRisc r ij

Risc r = dacă este un sistem cu o bază și atât j - jucător atunci când alege o strategie A i în condițiile H j se numește diferență b ,

o dacă este un sistem cu o bază și atât j Unde j- element maxim în

- a coloana.

Un grafic este o colecție de mulțimi nevide numite

mulţimea de vârfuri a graficului şi mulţimea de perechi de vârfuri, care se numesc

marginile graficului.

Dacă perechile de vârfuri luate în considerare sunt ordonate, atunci graficul

se numește orientat (digraf), altfel –

neorientat.

ÎN

Se numește o rută (cale) într-un grafic care leagă vârfurile A și B

succesiune de muchii, dintre care prima provine de la vârful A, începând

următorul coincide cu sfârșitul celui precedent, iar ultima muchie este inclusă în

sus V.

Un graf se numește conexat dacă pentru oricare două dintre vârfurile sale există o cale

conectându-le. În caz contrar, graficul se numește deconectat.

Un graf se numește finit dacă numărul vârfurilor sale este finit.

Dacă un vârf este începutul sau sfârșitul unei muchii, atunci vârful și muchia

se numesc incident. Gradul (ordinea) unui vârf este numărul de muchii incidente cu acesta.

O cale Euler (lanț eulerian) într-un grafic este o cale care trece prin toate

marginile graficului și, în plus, o singură dată.

Un ciclu eulerian este un drum eulerian care este un ciclu.

Un grafic eulerian este un grafic care conține un ciclu eulerian.

Un ciclu Euler există dacă și numai dacă graficul este conectat și în el

nu există vârfuri de grad impar.

Teorema. O cale Euler într-un grafic există dacă și numai dacă graficul

conectate și numărul de vârfuri de grad impar este zero sau două.

Un arbore este un grafic conex fără cicluri care are un vârf inițial

(rădăcină) și vârfuri extreme (gradul 1); căile de la vârful sursă la vârfurile exterioare se numesc ramuri.

O rețea (sau diagramă de rețea) este un finit orientat

un graf conectat care are un vârf inițial (sursă) și un vârf (sink) final.

Greutatea unei căi într-un grafic este suma greutăților marginilor sale.

Cea mai scurtă cale de la un vârf la altul va fi numită cale

greutate minima.

Greutatea acestei căi se va numi distanța dintre

culmi.

Munca este un proces consumator de timp care necesită resurse,

sau o dependență logică între două sau mai multe locuri de muncă

Un eveniment este rezultatul executării unuia sau mai multor lucrări

O cale este un lanț de lucrări succesive care se leagă

vârfuri de început și de sfârșit.

Durata călătoriei este determinată de suma duratelor

lucrările sale constitutive.

Reguli pentru intocmirea diagramelor de retea.

1. Nu ar trebui să existe evenimente de blocaj în diagrama de rețea (cu excepția

final), adică cele care nu sunt urmate de nicio lucrare.

2. Nu ar trebui să existe evenimente (cu excepția celui inițial) care să nu fie precedate de totuși

doar un loc de muncă.

3. Nu ar trebui să existe cicluri în diagrama de rețea.

4. Oricare două evenimente sunt conectate prin cel mult un job.

5. Diagrama rețelei trebuie să fie ordonată.

Orice cale al cărei început coincide cu evenimentul inițial și al cărui sfârșit coincide cu

terminarea se numește cale completă. Calea plina cu maxim

durata lucrării se numește calea critică

Ierarhia este un anumit tip de sistem bazat pe presupunerea că elementele sistemului pot fi grupate în seturi neînrudite

Descrierea metodei de analiză a ierarhiei

Construirea matricelor de comparație pe perechi

Găsiți lambda max și rezolvați sistemul în raport cu vectorul greutăților

Sinteza priorităților locale

Verificarea coerenței matricelor de comparație pe perechi

Sinteza priorităților globale

Evaluarea coerenței întregii ierarhii

Metoda simplex este o metodă de rezolvare a unei probleme de programare liniară. Esența metodei este de a găsi un plan fezabil inițial și, ulterior, de a îmbunătăți planul până când se atinge valoarea maximă (sau minimă) a funcției obiectiv într-o mulțime poliedrică convexă dată sau se determină imposibilitatea de rezolvare a problemei.

Luați în considerare următoarea problemă de programare liniară în formă canonică:

Metoda pe bază artificială

După cum se arată mai sus, pentru o problemă scrisă în formă canonică, dacă se află printre vectorii coloană ai matricei O Există m unitate și liniar independent, puteți specifica direct planul de referință. Cu toate acestea, pentru multe probleme de programare liniară scrise în formă canonică și având planuri de referință, printre vectorii coloane ai matricei O nu întotdeauna disponibil m unitar și liniar independent. Luați în considerare următoarea problemă:

Să presupunem că trebuie să găsim maximul unei funcții

in conditii

unde sunt primii n elementele sunt zero. Variabile sunt numite artificiale. Coloane de vectori

(28)

formează o așa-numită bază artificială m-spațiu vectorial dimensional.

Deoarece problema extinsă are un plan de referință, soluția ei poate fi găsită prin metoda simplex.

Teorema 4. Dacă în planul optim problema extinsă (24)−(26) valorile variabilelor artificiale , Asta este planul optim pentru problema (21)−(23).

Astfel, dacă în planul optim găsit pentru problema extinsă, valorile variabilelor artificiale sunt egale cu zero, atunci se obține planul optim pentru problema inițială. Să ne oprim mai detaliat asupra găsirii unei soluții la problema extinsă.

Valoarea funcției obiectiv pentru planul de referință (27):

Observăm că F(X)și constau din două părți independente, dintre care una este dependentă de M, iar celălalt - nu.

După calcul F(X) iar valorile acestora, precum și datele inițiale ale sarcinii extinse, sunt introduse într-un tabel simplex, așa cum se arată mai sus. Singura diferență este că acest tabel conține un rând în plus decât un tabel simplex obișnuit. În același timp, în ( m Linia +1) conține coeficienți care nu conțin M, și în ( m+2)-a linie − coeficienți pentru M.

La trecerea de la un plan de referință la altul, un vector care corespunde celui mai mare număr negativ în valoare absolută ( m+2) linii. Un vector artificial exclus din bază nu are sens să fie reintrodus în bază. Când treceți la un alt plan de referință, se poate întâmpla ca niciunul dintre vectorii artificiali să nu fie exclus din bază. Recalcularea tabelului simplex la trecerea de la un plan de referință la altul se efectuează conform regulilor obișnuite ale metodei simplex (vezi mai sus).

Procesul iterativ se realizează conform m+2 linie atâta timp cât elementele m+2 linii corespunzătoare variabilelor nu va deveni nenegativ. Mai mult, dacă variabilele artificiale sunt excluse din bază, atunci planul găsit al problemei extinse corespunde unui plan de referință al problemei inițiale.

m+2 rânduri, coloane x 0 este negativ, atunci problema inițială nu are soluție.

Dacă nu toate variabilele artificiale sunt excluse din bază și element m+2 rânduri, coloane x 0 este egal cu zero, atunci planul de referință al problemei inițiale este degenerat și baza conține cel puțin unul dintre vectorii bazei artificiale.

Dacă problema inițială conține mai mulți vectori unitari, atunci aceștia ar trebui să fie incluși în baza artificială.

Dacă în timpul iterațiilor m Linia +2 nu mai conține elemente negative, apoi procesul de iterație continuă cu m+1 linie, până când se găsește planul optim pentru problema extinsă sau se dezvăluie imposibilitatea de rezolvare a problemei.

Astfel, procesul de găsire a unei soluții la problema de programare liniară (21)−(23) folosind metoda bazei artificiale include următoarele etape principale:

• Compuneți problema extinsă (24)−(26).
• Găsiți planul de referință al problemei extinse.
• Folosind metoda simplex, vectorii artificiali sunt excluși din bază. Ca urmare, se găsește planul de referință al problemei inițiale sau se înregistrează insolubilitatea acesteia.
• Folosind planul de referință găsit al ZLP (21)−(23), ei fie găsesc planul optim al problemei inițiale, fie stabilesc insolubilitatea acesteia.

Pentru a rezolva probleme de programare liniară online, utilizați un calculator

Componentele modelului matematic

Baza pentru rezolvarea problemelor economice sunt modelele matematice.

Model matematic problema este un set de relații matematice care descriu esența problemei.

• selectarea variabilelor problemei
• elaborarea unui sistem de restricţii
• alegerea funcției obiective

Variabile de sarcină se numesc marimile X1, X2, Xn, care caracterizeaza complet procesul economic. Ele sunt de obicei scrise ca un vector: X=(X1, X2,...,Xn).

Sistemul de restricții problemele sunt un set de ecuații și inegalități care descriu resursele limitate din problema luată în considerare.

Funcția obiectivă sarcinile sunt numite o funcție a variabilelor sarcinii care caracterizează calitatea sarcinii și al căror 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=(X1, X2,...,Xn) cu condiția ca aceste variabile să satisfacă sistemul de restricții (2) și non-negativitatea condiţii (3).

Soluție valabilă(planul) unei probleme de programare liniară este orice vector n-dimensional X=(X1, X2,...,Xn) care satisface sistemul de constrângeri și condiții de non-negativitate.

Se formează setul de soluții (planuri) fezabile ale problemei regiune a soluțiilor fezabile(ODR).

Soluția optimă(planul) unei probleme de programare liniară este o astfel de soluție (plan) admisibilă a problemei în care funcția obiectiv atinge un extremum.

Stare: Pentru a produce n tipuri de produse se folosesc m tipuri de resurse. Creați un model matematic.

Cunoscut:

• bi (i = 1,2,3,...,m) - rezervele fiecărui i-lea tip de resursă;
• aij (i = 1,2,3,...,m; j=1,2,3,...,n) - costurile fiecărui i-a tip de resursă pentru producerea unei unități de volum de al j-lea tip de produs;
• cj (j = 1,2,3,...,n) - profit din vânzarea unei unități de volum de al j-lea tip de produs.

Este necesar să se întocmească un plan de producție care să asigure un profit maxim în limitele date privind resursele (materii prime).

Soluţie:

Să introducem un vector de variabile X=(X1, X2,...,Xn), unde xj (j = 1,2,...,n) este volumul de producție al celui de-al-lea tip de produs.

Costurile celui de-al i-lea tip de resursă pentru producerea unui anumit volum xj de produse sunt egale cu aijxj, prin urmare restricția privind utilizarea resurselor pentru producerea tuturor tipurilor de produse are forma:
Profitul din vânzarea celui de-al j-lea tip de produs este egal cu cjxj, 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 constrângerile să fie atât ecuații, cât și inegalități, iar variabilele pot fi fie nenegative, fie variabile în mod 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 - matricea coeficienților sistemului de ecuații
• X - matrice-coloană a variabilelor sarcinii
• Ао - matrice-coloană a părților drepte ale sistemului de restricții

Sunt adesea folosite probleme de programare liniară, numite simetrice, care în notația matriceală 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.

Să luăm inegalitatea liniară a1x1+a2x2+...+anxn≤b și să adăugăm la partea stângă o anumită valoare xn+1, astfel încât inegalitatea să se transforme în egalitatea a1x1+a2x2+...+anxn+xn+1=b . Mai mult, această valoare xn+1 este nenegativă.

Să privim totul folosind un exemplu.

Aduceți problema de programare liniară la forma canonică:

Soluţie:
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 transforma a doua și a treia inegalități ale sistemului de constrângeri în ecuații, introducem variabile suplimentare nenegative x4 x5 (în modelul matematic această operație este marcată cu litera D).
Variabila x4 este introdusă în partea stângă a celei de-a doua inegalități cu semnul „+”, deoarece inegalitatea are forma „≤”.
Variabila x5 este introdusă în partea stângă a celei de-a treia inegalități cu semnul „-”, deoarece inegalitatea are forma „≥”.
Variabilele x4 x5 sunt introduse în funcția obiectiv cu un coeficient. egal cu zero.
Scriem problema în formă canonică: