Mulțimi convexe și proprietățile lor. Pentru a studia proprietățile LPP, este necesar să se dea o definiție riguroasă a unei mulțimi convexe. Mai devreme, o mulțime convexă a fost definită ca o mulțime care, împreună cu oricare dintre punctele sale, conține un segment care le leagă.

O generalizare a conceptului de segment pentru mai multe puncte este combinația lor liniară convexă.

Punctul X este numit combinație liniară convexă puncte, dacă sunt îndeplinite condițiile

Setul de puncte este convex, dacă acesta, împreună cu oricare dintre cele două puncte ale sale, conține combinația lor convexă, liniară arbitrară.

Următoarea teoremă privind reprezentarea unui poliedru convex poate fi demonstrată.

Teorema 1.1. Un n-politop convex este o combinație liniară convexă a punctelor sale de colț.

Din teorema 1.1 rezultă că un poliedru convex este generat de punctele de colț sau vârfurile sale: un segment cu două puncte, un triunghi cu trei, un tetraedru cu patru puncte etc. În același timp, o regiune poliedrică convexă, fiind o mulțime nemărginită, nu este determinată în mod unic de punctele sale de colț: orice punct al acesteia nu poate fi reprezentat ca o combinație liniară convexă de puncte de colț.

Proprietățile problemei de programare liniară. Anterior, au fost luate în considerare diferite forme ale unei probleme de programare liniară și s-a demonstrat că orice problemă de programare liniară poate fi reprezentată ca o problemă generală sau canonică.

Pentru a fundamenta proprietățile unei probleme de programare liniară și metodele de rezolvare a acesteia, este recomandabil să luăm în considerare încă două tipuri de scriere a problemei canonice.

Notație matriceală:

Aici CU- matrice de rânduri, A- matricea sistemului, NS- matrice-coloană de variabile, V- matrice-coloana de membri liberi:

Notație vectorială:

unde vectorii corespund coloanelor de coeficienți pentru necunoscute.

Următoarea teoremă a fost enunțată mai sus, dar nu a fost demonstrată în formă generală.

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

Dovada: Lasa - două soluții admisibile ale LPP date sub formă de matrice. Apoi și . Luați în considerare o combinație liniară convexă de soluții, de ex.

și arătați că este și o soluție admisibilă pentru sistemul (1.3). Intr-adevar

adică soluţie X satisface sistemul (1.3). Dar de atunci NS> 0, adică soluţia satisface condiţia de non-negativitate.

Așadar, s-a dovedit că mulțimea tuturor soluțiilor admisibile ale problemei de programare liniară este convexă, sau, mai precis, reprezintă un poliedru convex sau un domeniu poliedric convex, care în cele ce urmează se va numi printr-un singur termen - poliedru de soluții.

Răspunsul la întrebarea în ce punct al politopului de soluții este soluția optimă pentru o problemă de programare liniară este posibil este dat în următoarea teoremă fundamentală.

Teorema 1.3. Dacă problema de programare liniară are o soluție optimă, atunci funcția liniară își ia valoarea maximă la unul dintre punctele de colț ale politopului soluției. Dacă o funcție liniară își ia valoarea maximă în mai multe puncte de colț, atunci o ia în orice punct care este o combinație liniară convexă a acestor puncte.

Dovada: Vom presupune că politopul soluției este mărginit. Să notăm punctele sale de colț cu , iar soluția optimă este prin X *... Atunci F (X *)³ F (X) pentru toate punctele NS poliedru de soluții. Dacă X * Este un punct de colț, atunci se demonstrează prima parte a teoremei.

Să ne prefacem că X * nu este un punct de colț, atunci prin Teorema 1.1 X * poate fi reprezentat ca o combinație liniară convexă de puncte de colț ale poliedrului de soluție, i.e.

pentru că F (X) Este o funcție liniară, obținem

În această expansiune, alegem valoarea maximă dintre valori. Lasă-l să corespundă punctului de colț X k(1 £ k£ R); să o notăm prin M, acestea. . Înlocuiți fiecare valoare din expresia (1.5) cu această valoare maximă M. Atunci

Prin presupunere NS* Este soluția optimă, așadar, pe de o parte, dar, pe de altă parte, este dovedit că
F (X *)£ M, deci unde X k- punct de colt. Deci există un punct de colț X kîn care funcția liniară își ia valoarea maximă.

Pentru a demonstra a doua parte a teoremei, presupunem că funcția obiectiv își ia valoarea maximă în mai multe puncte de colț, de exemplu, în punctele , Unde , atunci

Lasa NS- o combinație liniară convexă a acestor puncte de colț, i.e.

În acest caz, având în vedere că funcția F (X)- liniar, obținem

acestea. funcție liniară F ia valoarea maximă într-un punct arbitrar NS care este o combinație liniară convexă de puncte de colț.

Cometariu. Cerința ca politopul soluțiilor să fie mărginit în teoremă este esențială, deoarece în cazul unui domeniu poliedric nemărginit, așa cum s-a observat în teorema 1.1, nu fiecare punct al unui astfel de domeniu poate fi reprezentat printr-o combinație liniară convexă a punctelor sale de colț. .

Teorema demonstrată este fundamentală, deoarece indică o modalitate fundamentală de rezolvare a problemelor de programare liniară. Într-adevăr, conform acestei teoreme, în loc să studiem un set infinit de soluții fezabile pentru a găsi soluția optimă dorită între ele, este necesar să se investigheze doar un număr finit de puncte de colț ale poliedrului de soluții.

Următoarea teoremă este dedicată metodei analitice pentru găsirea punctelor de colț.

Teorema 1.4. Fiecare soluție de bază admisibilă a unei probleme de programare liniară corespunde unui punct de colț al politopului de soluție și invers, fiecărui punct de colț al poliedrului de soluție îi corespunde o soluție de bază admisibilă.

Dovada: Fie o soluție de bază admisibilă a sistemului de constrângeri LPP (1.4), în care prima T componenta este variabilele principale iar restul n - t componentă - variabile minore egale cu zero în soluția de bază (dacă nu este cazul, atunci variabilele corespunzătoare pot fi renumerotate). Să arătăm asta NS

Să presupunem contrariul, adică. ce NS nu este un punct de colț. Apoi punctul NS poate fi reprezentat printr-un punct interior al unui segment care leagă două diferite care nu coincid cu X, puncte

cu alte cuvinte, o combinație liniară convexă de puncte poliedru de soluții, adică

unde (presupunem că, în caz contrar, punctul NS coincide cu punctul NS 1 sau NS 2).

Scriem egalitatea vectorială (1.6) sub formă de coordonate:

pentru că toate variabilele și coeficienții sunt nenegativi, apoi de la cei din urmă p-t egalități rezultă că, i.e. în decizii NS 1 , NS 2 și NS sistem de ecuații (1.4) valorile n - t componentele sunt egale în acest caz cu zero. Aceste componente pot fi considerate ca valori ale variabilelor minore. Dar valorile variabilelor minore determină fără ambiguitate valorile celor majore, prin urmare,

Deci toate NS componentă în soluții NS 1 , NS 2 și NS coincid și deci punctele NS 1 și NS 2 fuzionează, ceea ce contrazice presupunerea. Prin urmare, X Este punctul de colț al poliedrului soluție.

Să demonstrăm afirmația inversă. Fie punctul de colț al politopului de soluții și primul său T coordonatele sunt pozitive. Să arătăm asta NS- soluţie de bază admisibilă. nu este un punct de colț, ceea ce contrazice condiția. Prin urmare, presupunerea noastră este incorectă, adică vectorii sunt independenți liniar și NS Este o soluție de bază admisibilă a problemei (1.4).

Un corolar important rezultă direct din teoremele 1.3 și 1.4: dacă o problemă de programare liniară are o soluție optimă, atunci ea coincide cu cel puțin una dintre soluțiile sale de bază admisibile.

Asa de, optimul unei funcții liniare a unei probleme de programare liniară ar trebui căutat între un număr finit de soluții de bază admisibile.

Se realizează optimizarea modelelor liniare în MS Excel metoda simplex- enumerarea intenţionată a soluţiilor suport ale problemei de programare liniară. Algoritmul metodei simplex se reduce la construirea unui poliedru convex într-un spațiu multidimensional, iar apoi la iterarea peste vârfurile acestuia pentru a găsi valoarea extremă. funcție obiectivă.

Remedii eficiente programare liniară stau la baza programării întregi și neliniare pentru probleme de optimizare mai complexe. Cu toate acestea, aceste metode necesită un timp de calcul mai lung.

În prelegerile ulterioare, vor fi analizate în detaliu exemple de rezolvare a problemelor tipice de optimizare și de luare a deciziilor de management folosind programul de completare MS Excel „Căutare soluție”. Sarcinile care sunt cel mai bine îndeplinite de acest instrument au trei proprietăți principale:

• există un singur scop, legat funcțional de alți parametri ai sistemului, care trebuie optimizat (găsește-i valoarea maximă, minimă sau o anumită valoare numerică);
• există restricții, de obicei exprimate sub formă de inegalități (de exemplu, volumul de materii prime utilizate nu poate depăși stocul de materii prime din depozit, sau timpul de funcționare al mașinii pe zi nu trebuie să depășească 24 de ore minus timpul pentru serviciu);
• există un set de valori ale variabilelor de intrare care afectează valorile și constrângerile optimizate.

Parametrii sarcinii sunt limitați de următoarele valori limită:

• număr de necunoscute - 200;
• numărul de constrângeri de formulă pe necunoscute - 100;
• numărul de condiții limită pentru necunoscute este 400.

Algoritmul pentru găsirea soluțiilor optime include mai multe etape:

• munca pregatitoare;
• depanarea soluției;
• analiza solutiei.

Secvența lucrărilor pregătitoare necesare efectuate în rezolvarea problemelor de modelare economică și matematică folosind MS Excel este prezentată în schema bloc din Figura 1.6.

Orez. 1.6.

Din cele cinci puncte ale planului de lucru pregătitor, doar al cincilea punct este oficializat. Restul lucrărilor necesită creativitate - și pot fi făcute în moduri diferite de către diferiți oameni. Să explicăm pe scurt esența formulării punctelor planului.

La stabilirea problemei, se cunosc coeficienții țintă și coeficienții normalizați. În exemplul anterior, coeficienții care formează funcția obiectiv au fost valorile profitului normalizat pe raft de tip ( ) și un raft de tip ( ). Coeficienții normalizați au fost ratele de consum de material și timpul de mașină pe raft de fiecare tip. Matricea arăta astfel:

În plus, valorile resurselor sunt întotdeauna cunoscute. În exemplul anterior, era o aprovizionare săptămânală de plăci și capacitatea de a folosi timpul mașinii: , ... Adesea, în sarcini, valorile variabilelor trebuie limitate. Prin urmare, este necesar să se determine limitele inferioare și superioare ale zonei modificărilor lor.

Astfel, în caseta de dialog a programului de optimizare „Căutare soluție”, trebuie să specificăm următorul algoritm țintă:

Funcția obiectiv este egală cu produsul dintre vectorul valorilor dorite ale variabilelor cu vectorul coeficienților obiectivi

Coeficienții normalizați pentru vectorul valorilor căutate ale variabilelor nu trebuie să depășească valoarea vectorului dat de resurse

Valorile variabilei trebuie să se încadreze în limitele specificate ale numărului de elemente inițiale ale sistemului

Numărul de elemente inițiale ale sistemului

Numărul de tipuri specificate de resurse

Depanarea soluției este necesară în cazul în care programul emite un mesaj despre rezultate negative (Figura 1.7):

Orez. 1.7.

• dacă nu se obține o soluție fezabilă, atunci corectați modelul datelor inițiale;
• dacă nu este primită soluție optimă, apoi introduceți restricții suplimentare.

Problemele programului soluție optimă doar pentru a modela o problemă reală, nu o soluție a problemei în sine. La construirea modelului s-au făcut diverse ipoteze simplificatoare ale situației reale. Acest lucru a făcut posibilă formalizarea procesului, reflectând aproximativ relațiile cantitative reale dintre parametrii sistemului și scop. Și dacă parametrii reali diferă de cei incluși în model, cum se va schimba decizia? Pentru a afla, înainte de a lua o decizie de management, se analizează un model de decizie.

Analiză soluție optimă, încorporat în program, este etapa finală a modelării matematice a proceselor economice. Permite o verificare mai aprofundată a adecvării modelului la proces, precum și a fiabilității soluției optime. Este bazat pe date soluție optimăși rapoarte care sunt emise în „Căutare soluție”. Dar nu exclude sau înlocuiește analiza tradițională a planului din punct de vedere economic înainte de a lua o decizie de management.

Analiza economică are următoarele obiective:

• determinarea consecințelor posibile în sistemul în ansamblu și elementele acestuia la modificarea parametrului modelului;
• evaluarea stabilității planului optim la modificările parametrilor individuali ai problemei: dacă nu este rezistent la modificările majorității parametrilor, garanția implementării sale și atingerea optimului calculat scade;
• efectuarea de calcule de variante și obținerea de noi variante ale planului fără a re-rezolva problema de la baza inițială prin ajustări.

Metodele posibile de analiză sunt prezentate în diagrama din Figura 1.8.

După primirea soluției optime, aceasta este analizată conform rapoartelor primite. Analiza stabilității- studiul influenței modificărilor parametrilor individuali ai modelului asupra indicatorilor soluției optime. Analiza limitelor- analiza modificărilor acceptabile în planul optim, în care planul rămâne optim.

Având în vedere responsabilitatea de a face economic decizie de management, liderul trebuie să se asigure că planul optim primit este singurul corect. Pentru a face acest lucru, este necesar să obțineți răspunsuri la următoarele întrebări pe baza modelului:

• "ce-ar fi dacă…"
• "ce este necesar pentru..."

Se numește analiza pentru a răspunde la prima întrebare analiza variantelor; se numește analiza pentru a răspunde la a doua întrebare solutii personalizate.

Analiza variantelor este de următoarele tipuri:

• Parametric- analiza, care constă în rezolvarea unei probleme pentru diferite valori ale unui anumit parametru.
• Analiză structurală- când se caută soluţia problemei de optimizare cu o structură diferită de constrângeri.
• Analiza multicriteriala- Aceasta este o soluție la problema pentru diferite funcții țintă.
• Analiză cu date de intrare condiționate- când datele iniţiale folosite în rezolvarea problemei depind de respectarea unor condiţii suplimentare.

După analiză, rezultatele trebuie prezentate în formă grafică și trebuie întocmit un raport cu recomandări pentru luarea unei decizii, ținând cont de situația economică specifică.

Definiție... Orice soluție a sistemului de constrângeri se numește soluție admisibilă a LPP.
Definiție... O soluție fezabilă în care funcția obiectiv își atinge valoarea maximă sau minimă se numește soluție optimă.

În virtutea acestor definiții, problema LP poate fi formulată după cum urmează: dintre toate punctele unei regiuni convexe care este o soluție a sistemului de constrângeri, alegeți unul ale cărui coordonate minimizează (maximizează) funcția liniară F = cu 1 X + cu 2 y.
Rețineți că variabilele X, yîn LPP iau, de regulă, valori nenegative ( X≥ 0, y≥ 0), deci regiunea este situată în sfertul I al planului de coordonate.

Luați în considerare o funcție liniară F = cu 1 X + cu 2 yși fixați unele dintre valorile sale F... Să, de exemplu, F= 0, adică cu 1 X + cu 2 y= 0. Graficul acestei ecuații va fi o dreaptă care trece prin originea coordonatelor (0; 0) (Fig.).
Desen
La modificarea acestei valori fixe F = d, Drept cu 1 X+ cu 2 y = d se va deplasa în paralel și „urma” întregul plan. Lasa D- poligon - zona de rezolvare a sistemului de constrângeri. Când se schimbă d Drept cu 1 X + cu 2 y = d, la o oarecare valoare d = d 1 va ajunge la poligon D, să numim acest punct A„Punctul de intrare”, și apoi, trecând poligonul, la o anumită valoare d = d 2 vom avea ultimul punct comun cu acesta V, Hai sa sunăm V„Punctul de ieșire”.
Evident, funcția obiectivă a valorii sale cele mai mici și mai mari F=cu 1 X + cu 2 y va ajunge la punctele de intrare Ași „ieșire” V.
Ținând cont de faptul că funcția obiectiv ia valoarea optimă pe setul de soluții fezabile la vârfurile regiunii D, se poate propune următorul plan de rezolvare a LPP:

1. pentru a construi zona de soluții a sistemului de restricții;
2. construiți o linie dreaptă corespunzătoare funcției obiectiv și prin transferul paralel al acestei linii drepte găsiți punctul de „intrare” sau „ieșire” (în funcție de cerința de a minimiza sau maximiza funcția obiectiv);
3. determinați coordonatele acestui punct, calculați valoarea funcției obiectiv în ele.

Rețineți că vectorul ( cu 1 , cu 2), perpendicular pe dreapta, arată direcția de creștere a funcției obiectiv.

La rezolvarea grafică a LPP-ului, există două cazuri posibile care necesită o discuție specială.

Cazul 1
Figura 6
Când vă deplasați drept cu 1 X + cu 2 y= d„Intrarea” sau „ieșirea” (ca în imagine) va avea loc pe partea laterală a poligonului. Acest lucru se va întâmpla dacă poligonul are laturile paralele cu o linie dreaptă. cu 1 NS+ cu 2 la = d .
În acest caz, punctele de „ieșire” („intrare”) sunt nenumărate, și anume orice punct al segmentului AB... Aceasta înseamnă că funcția obiectiv ia valoarea maximă (minimă) nu într-un punct, ci în toate punctele situate pe latura corespunzătoare a poligonului. D.

Cazul 2
Luați în considerare cazul în care intervalul de valori admisibile este nelimitat.
În cazul unei zone nemărginite, funcția obiectiv poate fi specificată în așa fel încât linia dreaptă corespunzătoare să nu aibă un punct de „ieșire” (sau „intrare”). Atunci valoarea maximă a funcției (minima) nu este niciodată atinsă - se spune că funcția nu este limitată.
Desen
Este necesar să se găsească valoarea maximă a funcției obiectiv F = 4X + 6y→ max, cu un sistem de restricții
Să construim regiunea soluțiilor fezabile, i.e. vom rezolva grafic sistemul de inegalităţi. Pentru a face acest lucru, construim fiecare dreaptă și definim semiplanurile date de inegalități.
X + y = 18

X	12	9
y	6	9

0,5X + y = 12

X	12	18
y	6	3

X= 12 - paralel cu axa OY ;
y= 9 - paralel cu axa BOU ;
X= 0 - axa OY ;
y = 0 - axa BOU;
X OY;
y≥ 0 - semiplan deasupra axei BOU;
y≤ 9 - semiplan dedesubt y = 9;
X ≤ 12 - semiplan spre stânga X = 12;
0,5X + yX + y = 12;
X + y X + y = 18.
Desen
Intersecția tuturor acestor semiplanuri este evident pentagonul OAVSD, cu vârfuri în puncte O(0; 0), A(0; 9), V(6; 9), CU(12; 6), D(12; 0). Acest pentagon formează regiunea soluțiilor fezabile ale problemei.

F = 4X + 6y→ max.

X	3	0
y	–2	0

F = 0: 4X + 6y X+ 6y CU(12; 6). Este în ea F = 4X + 6y
Prin urmare, pentru X = 12, y= 6 funcția F F= 4 ∙ 12 + 6 ∙ 6 = 84, egal cu 84. Punctul cu coordonatele (12; 6) satisface toate inegalitățile sistemului de constrângeri, iar valoarea funcției obiectiv din acesta este optimă F* = 84 (valoarea optimă va fi notată cu „*”).
Problema a fost rezolvată. Deci, este necesar să se producă 12 produse de tip I și 6 produse de tip II, în timp ce profitul va fi de 84 de mii de ruble.

Metoda grafică este folosită pentru a rezolva probleme care aveau doar două variabile în sistemul de restricții. Această metodă poate fi aplicată și sistemelor de inegalități cu trei variabile. Geometric, situația va fi diferită, rolul liniilor drepte va fi jucat de planuri în spațiul tridimensional, iar soluția inegalității în trei variabile va fi un semispațiu situat pe o parte a planului. Rolul regiunilor va fi jucat de poliedre, care sunt intersecția semi-spațiilor.

Exemplul nr. 2. Mina dezvoltă două cusături. Ieșirea tăieturii în primul strat este de 1%; pe al doilea - a2%. Producția maximă a peretelui lung pentru primul strat este de B1 mii de tone pe an, pentru al doilea strat - B2 mii de tone pe an. Conform tehnologiei de lucru, producția din al doilea strat nu poate depăși producția din primul strat. Producția minei în mină nu trebuie să depășească C1 mie tone pe an. Sarcina totală pe cele două straturi pe an ar trebui să fie de cel puțin C2 mii de tone pe an. Creați un model matematic și construiți un set de valori de încărcare permise pentru primul și al doilea strat pe an.

Exemplul nr. 3. Magazinul comercializeaza 2 tipuri de bauturi racoritoare: Cola si limonada. Venitul dintr-o cutie de cola este de 5 cenți, în timp ce venitul dintr-o cutie de limonada este de 7 cenți. În medie, un magazin vinde nu mai mult de 500 de cutii din ambele băuturi pe zi. În ciuda faptului că cola este produsă de un brand cunoscut, cumpărătorii preferă limonada pentru că este mult mai ieftină. Se estimează că vânzările de cola și limonadă ar trebui să fie de cel puțin 2: 1, iar magazinul este cunoscut că vinde cel puțin 100 de cutii de cola pe zi. Câte cutii din fiecare băutură ar trebui să aibă magazinul la începutul zilei pentru a maximiza veniturile?

Exemplul nr. 4. Rezolvați problema de programare liniară aproximativ grafic cu calculul ulterior al valorii exacte și max (min) a valorii funcției obiectiv.

Exemplul nr. 5. O agenție de turism necesită autobuze de cel mult trei tone și autobuze de cinci tone. Prețul de vânzare al autobuzelor de prima marcă este de 20.000 USD, a doua marcă este de 40.000 USD. O agenție de turism poate aloca pentru achiziționarea de autobuze nu mai mult de 1 dolar. Câte autobuze de fiecare marcă ar trebui achiziționate separat, astfel încât capacitatea lor totală (totală) de transport să fie maximă. Rezolvați problema grafic.

Exemplul nr. 6. Folosind metoda grafică, găsiți planul optim de producție pentru sarcina prezentată în tabel.

Exemplul nr. 7. Rezolvați problema de programare liniară printr-o metodă grafică, supunând sistemul de constrângeri al problemei transformărilor Jordan-Gauss. Sistemul de constrângeri problemei este următorul:
a 11 x 1 + a 12 x 2 + a 13 x 3 + a 14 x 4 + a 15 x 5 = b 1
a 21 x 1 + a 22 x 2 + a 23 x 3 + a 24 x 4 + a 25 x 5 = b 2
a 31 x 1 + a 32 x 2 + a 33 x 3 + a 34 x 4 + a 35 x 5 = b 3
Instrucțiuni... Transformările Jordan-Gauss pot fi efectuate folosind acest serviciu sau prin studiul SLAE-urilor.

Exemplul nr. 8. Întreprinderea produce două tipuri de produse, A și B, pentru producția cărora se folosesc trei tipuri de materii prime. Pentru fabricarea unei unități de produs A, este necesar să cheltuiți materii prime de fiecare tip a1, a2, respectiv a3 kg, iar pentru o unitate de produs B - b1, b2, b3 kg. Producția este asigurată cu materii prime de fiecare tip în cantitate de Р1, Р2, Р3 kg. Costul unei unități de produs A este C1 ruble, iar unitatea de produs B este C2 ruble. Este necesar să se întocmească un plan de producție a produselor A și B, care să asigure costul maxim al produsului finit.

Exemplul nr. 2. Este necesar să se găsească valoarea maximă a funcției obiectiv F = 4X + 6y→ max, cu un sistem de restricții:

Să construim regiunea soluțiilor fezabile, i.e. vom rezolva grafic sistemul de inegalităţi. Pentru a face acest lucru, selectați numărul de restricții egal cu 4 (Figura 1).
Poza 1

Apoi completăm coeficienții pentru variabile și constrângerile în sine (Figura 2).
Poza 2

Figura 3
X= 12 - paralel cu axa OY;
y= 9 - paralel cu axa BOU;
X> = 0 - axa OY
y= 0 - axa BOU;
X≥ 0 - semiplan la dreapta axei OY;
y≥0 - semiplan deasupra axei BOU;
y≤ 9 - semiplan dedesubt y = 9;
X≤ 12 - semiplan spre stânga X = 12;
0,5X + y≤ 12 - semiplan sub o dreaptă 0,5 X + y = 12;
X + y≤ 18 - semiplan sub linia dreaptă X + y = 18.

Intersecția tuturor acestor semiplane este pentagonul ABCDE, cu vârfuri în puncte A(0; 0), B(0;9), C(6; 9), D(12;6), E(12; 0). Acest pentagon formează regiunea soluțiilor fezabile ale problemei.

Luați în considerare funcția obiectivă a problemei F = 4X + 6y→ max.

X	3	0
y	–2	0

Construim o linie dreaptă corespunzătoare valorii funcției F = 0: 4X + 6y= 0. Vom muta această linie în mod paralel. Din întreaga familie de linii, 4 X + 6y= const ultimul vârf prin care trece linia dreaptă când depășește limita poligonului va fi vârful CU(12; 6). Este în ea F = 4X + 6y atinge valoarea sa maximă.

Prin urmare, pentru X = 12, y= 6 funcția F atinge valoarea sa maximă F= 4 ∙ 12 + 6 ∙ 6 = 84, egal cu 84. Punctul cu coordonatele (12; 6) satisface toate inegalitățile sistemului de constrângeri, iar valoarea funcției obiectiv din acesta este optimă F* = 84.

Test la disciplina „Cercetare operațională”

(răspunsurile corecte sunt primele)

1. Termenul „cercetare operațională” a apărut...

în timpul celui de-al doilea război mondial

în anii '50 ai secolului XX

în anii 60 ai secolului XX

în anii 70 ai secolului XX

în anii 90 ai secolului XX

la începutul secolului XXI

2. Mijloace de cercetare operațională (alegeți cea mai potrivită variantă) ...

un set de metode științifice pentru rezolvarea problemelor de management eficient al sistemelor organizaționale

un set de măsuri luate pentru implementarea anumitor operațiuni

un set de metode de implementare a planului conceput

metode științifice de alocare a resurselor în organizarea producției

3. Aranjați pașii prin care parcurge de obicei orice cercetare operațională:

formularea problemei

construirea unui model semnificativ (verbal) al obiectului (procesului) considerat

construirea unui model matematic

rezolvarea de probleme formulate pe baza modelului matematic construit

verificarea rezultatelor obţinute pentru adecvarea naturii sistemului studiat

implementarea în practică a soluției obținute

4. În cercetarea operațională, o operațiune se înțelege ...

orice eveniment (sistem de acțiuni), unite printr-un singur concept și care vizează atingerea unui scop

orice eveniment incontrolabil

un set de măsuri tehnice pentru asigurarea producţiei de produse de consum

5. Soluția se numește optimă, ...

dacă este de preferat dintr-un motiv sau altul

dacă este raţional

daca se convine cu autoritatile

dacă este aprobat de adunarea generală

6. Programare matematică...

este angajat în studiul problemelor extreme și în dezvoltarea metodelor de rezolvare a acestora

este procesul de creare a programelor de calculator sub îndrumarea matematicienilor

rezolvă probleme matematice pe calculator

7. Sarcina programării liniare este...

găsirea celei mai mari (mai mici) valori a unei funcții liniare în prezența constrângerilor liniare

crearea unui program liniar într-un limbaj de programare selectat menit să rezolve problema

descrierea unui algoritm liniar pentru rezolvarea unei probleme date

8. Într-o problemă de programare pătratică...

funcția obiectiv este pătratică

aria soluțiilor admisibile este un pătrat

constrângerile conţin funcţii pătratice

9. În problemele de programare cu numere întregi...

necunoscutele pot lua numai valori întregi

funcția obiectiv trebuie să ia în mod necesar o valoare întreagă, iar necunoscutele pot fi oricare

funcția țintă este o constantă numerică

10. În sarcinile de programare parametrică...

funcția obiectiv și/sau sistemul de constrângeri conține parametru(i)

aria soluțiilor admisibile este un paralelogram sau paralelipiped

numărul de variabile poate fi doar par

11. În problemele de programare dinamică...

procesul de găsire a unei soluții este în mai multe etape

necesitatea de a raționaliza producția de dinamită

doriți să optimizați utilizarea difuzoarelor

12. Se pune următoarea problemă de programare liniară:

F(NS 1, NS 2) = 5NS 1 + 6NS 2→ max

0.2NS 1 + 0.3NS 2 ≤ 1.8,

0.2NS 1 + 0.1NS 2 ≤ 1.2,

0.3NS 1 + 0.3NS 2 ≤ 2.4,

NS 1 ≥ 0, NS 2 ≥ 0.

Selectați o sarcină care este echivalentă cu această sarcină.

F(NS 1, NS 2)= 5NS 1 + 6NS 2 → max,

2NS 1 + 3NS 2 ≤ 18,

2NS 1 + NS 2 ≤ 12,

NS 1 + NS 2 ≤ 8,

NS 1 ≥ 0,

NS 2 ≥ 0.

F(NS 1, NS 2)= 6NS 1 + 5NS 2 → min,

2NS 1 + 3NS 2 ≤ 18,

2NS 1 + NS 2 ≤ 12,

NS 1 + NS 2 ≤ 8,

NS 1 ≥ 0,

NS 2 ≥ 0.

F(NS 1, NS 2)= 50NS 1 + 60NS 2 → max,

2NS 1 + 3NS 2 ≤ 18,

2NS 1 + NS 2 ≤ 12,

NS 1 + NS 2 ≤ 8,

NS 1 ≥ 0,

NS 2 ≥ 0.

F(NS 1, NS 2)= 5NS 12 + 6NS 22 → max,

2NS 1 + 3NS 2 ≤ 18,

2NS 1 + NS 2 ≤ 12,

3NS 1 + NS 2 ≤ 2.4,

NS 1 ≥ 0,

NS 2 ≥ 0.

13. Funcția obiectiv a unei probleme de programare liniară poate fi funcția:

F=12x1+20x2-3 0x3→min

F= →min

F=→max

F=→max.

14. Sistemul de constrângeri al problemei de programare liniară poate fi sistemul:

15. Metoda simplex este:

metoda analitica de rezolvare a problemei principale a programarii liniare

o metodă pentru găsirea regiunii soluțiilor fezabile la o problemă de programare liniară;

o metodă grafică pentru rezolvarea problemei principale a programării liniare;

o metodă pentru reducerea unei probleme generale de programare liniară la o formă canonică.

16. Sarcina programării liniare este:

găsirea celei mai mari sau mai mici valori a unei funcții liniare în prezența constrângerilor liniare

dezvoltarea unui algoritm liniar și implementarea lui pe calculator

întocmirea şi rezolvarea unui sistem de ecuaţii liniare

căutarea unei traiectorii liniare a desfăşurării procesului descris de un sistem dat de restricţii.

17. Domeniul soluțiilor fezabile ale problemei de programare liniară nu poti arata asa:

18. Funcția țintă a unei probleme de programare liniară poate fi funcția:

F=12x1+20x2-3 0x3→min

F= →min

F=→max

F=→max.

19. Sistemul de constrângeri al problemei de programare liniară poate fi sistemul:

20. Regiunea soluțiilor fezabile ale problemei de programare liniară este următoarea:

F(NS 1, NS 2)= 3NS 1 + 5NS 2 este egal...

21. Regiunea soluțiilor fezabile ale problemei de programare liniară are forma:

Apoi valoarea maximă a funcției F(NS 1, NS 2)= 5NS 1 + 3NS 2 este egal...

22. Regiunea soluțiilor fezabile ale problemei de programare liniară are forma:

Apoi valoarea maximă a funcției F(NS 1, NS 2)= 2NS 1 - 2NS 2 este egal...

23. Regiunea soluțiilor fezabile ale problemei de programare liniară are forma:

F(NS 1, NS 2)= 2NS 1 - 2NS 2 este egal...

24. Regiunea soluțiilor fezabile la problema programării neliniare are forma:

Apoi valoarea maximă a funcției F(NS 1, NS 2)= NS 2 – NS 12 este egal...

25. Valoarea maximă a funcției obiectiv F(NS 1, NS 2)= 5NS 1 + 2NS 2 cu restricții
NS 1 + NS 2 ≤ 6,

NS 1 ≤ 4,

NS 1 ≥ 0, NS 2 ≥ 0, este egal cu...

26. O afacere mică produce produse de două tipuri. Pentru fabricarea unui produs de tip A se consumă 2 kg de materii prime, pentru fabricarea unui produs de tip B - 1 kg. Sunt 60 kg de materii prime in total. Este necesar să se întocmească un plan de producție care să asigure primirea celor mai mari încasări, dacă costul de vânzare al unui produs de tip A este de 3 c. E., Tipul B este de 1 y. Adică, produsele de tip A nu trebuie făcute mai mult de 25, iar tipul B - nu mai mult de 30.

Această sarcină este...

problema de programare liniara

problema rezolvată prin metoda de programare dinamică

sarcina de planificare a rețelei.

27. O afacere mică produce produse de două tipuri. Pentru fabricarea unui produs de tip A se consumă 2 kg de materii prime, pentru fabricarea unui produs de tip B - 1 kg. Sunt 60 kg de materii prime in total. Este necesar să se întocmească un plan de producție care să asigure primirea celor mai mari încasări, dacă costul de vânzare al unui produs de tip A este de 3 c. E., Tipul B este de 1 y. Adică, produsele de tip A nu trebuie făcute mai mult de 25, iar tipul B - nu mai mult de 30.

Funcția obiectivă a acestei sarcini este funcția...

F(x1, x2)=3x1+x2→max

F(x1, x2)=25x1+30x2→max

F(x1, x2)=2x1+x2→max

F(x1, x2)=60 -2x1 - x2→min

28. O afacere mică produce produse de două tipuri. Pentru fabricarea unui produs de tip A se consumă 2 kg de materii prime, pentru fabricarea unui produs de tip B - 1 kg. Sunt 60 kg de materii prime in total. Este necesar să se întocmească un plan de producție care să asigure primirea celor mai mari încasări, dacă costul de vânzare al unui produs de tip A este de 3 c. E., Tipul B este de 1 y. Adică, produsele de tip A trebuie să fie fabricate nu mai mult de 25, iar tipul B - nu mai mult de 30

Un plan valid pentru această sarcină este un plan:

X =(20, 20)

X =(25, 15)

X =(20, 25)

X =(30, 10)

29. În două puncte A1 și A2, există 60 și respectiv 160 de unități de mărfuri. Toate bunurile trebuie transportate la punctele B1, B2, B3 în valoare de 80, 70 și, respectiv, 70 de unități. Matricea tarifară este următoarea:. Planificați transportul astfel încât costul să fie minim.

Această sarcină este...

sarcina de transport

problema de programare neliniară

problema vânzătorului ambulant

sarcina de atribuire

30. În două puncte A1 și A2, există 60 și respectiv 160 de unități de mărfuri. Toate bunurile trebuie transportate la punctele B1, B2, B3 în valoare de 80, 70 și, respectiv, 70 de unități. Matricea tarifară este următoarea:. Planificați transportul astfel încât costul să fie minim

Planul de bază pentru această sarcină este planul:

;

31. În două puncte A1 și A2, există 60 și, respectiv, 160 de unități de mărfuri. Toate bunurile trebuie transportate la punctele B1, B2, B3 în valoare de 80, 70 și, respectiv, 70 de unități. Matricea tarifară este următoarea:. Planificați transportul astfel încât costul să fie minim.

Funcția obiectivă a acestei sarcini este funcția:

F=4x11+6x12 + 8x13+5x21+8x22+7x23→min

F= →min

F=60x1+160x2 + 80x3+70x4+705 →max

F=60x1+160x2– 80x3– 70x4– 705 →min

32. În două puncte A1 și A2, există 60 și respectiv 160 de unități de mărfuri. Toate bunurile trebuie transportate la punctele B1, B2, B3 în valoare de 80, 70 și, respectiv, 70 de unități. Matricea tarifară este următoarea:. Planificați transportul astfel încât costul să fie minim.

Planul optim pentru această sarcină este planul:

;

.

;

;

33. Problema transportului

va fi închis dacă...

34. Problema transportului

este un…

deschis

închis

insolubil

35. Problema transportului

este un…

închis

deschis

insolubil

36. Pentru a rezolva următoarea problemă de transport

trebuie sa intri...

consumator fictiv

furnizor fictiv;

tarif efectiv

37. Pentru a rezolva următoarea problemă de transport

trebuie sa intri...

furnizor fictiv;

consumator fictiv

tarif efectiv

rata efectivă a dobânzii.

38. Printre aceste sarcini de transport

inchise sunt...

39. Planul de referință inițial al problemei transportului poate fi întocmit...

prin toate metodele de mai sus

Metoda colțului de nord-vest

prin metoda tarifului minim

metoda preferintei duble

prin metoda aproximării Vogel

40. Dacă funcția obiectiv a problemei de programare liniară este setată la maxim, atunci ... funcția obiectiv a problemei duale este setată la minim

nu există nicio funcție obiectivă în problema duală

problema duala nu are solutii

problema duală are infinit de soluții

41. O problemă de programare liniară este dată:

F(NS 1, NS 2)= 2NS 1 + 7NS 2 → max,

2NS 1 + 3NS 2 ≤ 14,

NS 1 + NS 2 ≤ 8,

NS 1 ≥ 0, NS 2 ≥ 0.

Următoarele vor fi duble pentru această sarcină...

F *(y1, y2) = 14y1 + 8y2 → min,

3 ani 1 + y2 ³ 7,

y 1 ≥ 0, y2 ≥ 0.

F *(y1, y2) = 2y1 + 7y2 → min,

2y1 + 3y2 ³ 14,

y 1 + y2 ³ 8,

y 1 £ 0, y2 £ 0.

F *(y1, y2) = 2y1 + 7y2 → min,

3 y 1 + y2 ³ 7,

y 1 £ 0, y2 £ 0.

F *(y1, y2) = 14y1 + 8y2 → min,

y 1 + y2 ³ 7,

y 1 ≥ 0, y2 ≥ 0.

42. Dacă una dintr-o pereche de probleme duale are un plan optim, atunci...

iar celălalt are un plan optim

celălalt nu are un plan optim

celălalt nu are soluții fezabile

43. Dacă una din perechea de probleme duale are un plan optim, atunci ...

iar celălalt are un plan optim, iar valorile funcțiilor obiective pentru planurile lor optime sunt egale între ele

iar celălalt are un plan optim, dar valorile funcțiilor obiective pentru planurile lor optime nu sunt egale între ele

o altă problemă poate să nu aibă un plan optim, dar să aibă soluții fezabile

44. Dacă funcția obiectiv a uneia din perechile de probleme duale nu este mărginită (pentru problema maximă - de sus, pentru problema minimă - de jos), atunci

o altă sarcină nu are planuri valide

o altă sarcină are planuri fezabile, dar nu are un plan optim

nici funcția obiectivă a unei alte sarcini nu este limitată

45. La rezolvarea unor probleme de programare neliniară se folosește ...

Metoda multiplicatorului Lagrange

metoda Gauss

Metoda de aproximare Vogel

metoda Gomori

46. ​​​​Se pune problema programării neliniare

F(NS 1, NS 2)= NS 12 + NS 22 → max,

NS 1 + NS 2 =6,

NS 1 ≥ 0, NS 2 ≥ 0.

F(NS 1, NS 2) …

nu este accesibil (+ ¥)

47. Problema programării neliniare este pusă

F(NS 1, NS 2)= NS 12 + NS 22 → mîn,

NS 1 + NS 2 =6,

NS 1 ≥ 0, NS 2 ≥ 0.

F(NS 1, NS 2) …

48. Problema programării neliniare este pusă

F(NS 1, NS 2)= NS 12 + NS 22 → max,

NS 1 + NS 2 =6,

NS 1, NS 2 - oricare.

Cea mai mare valoare a funcției obiectiv F(NS 1, NS 2) …

nu este accesibil (+ ¥)

49. Problema programării neliniare este pusă

F(NS 1, NS 2)= NS 12 + NS 22 → mîn,

NS 1 + NS 2 =6,

NS 1, NS 2 - oricare.

Cea mai mică valoare a funcției obiectiv F(NS 1, NS 2) …

nu este accesibil (- ¥)

50. Regiunea soluțiilor fezabile la problema programării neliniare are forma:

Apoi valoarea maximă a funcției F(NS 1, NS 2)= NS 12 +NS 22 este egal...

51. Regiunea soluțiilor fezabile la problema programării neliniare are forma:

Apoi valoarea minimă a funcției F(NS 1, NS 2)= NS 12 +NS 22 este egal...

52. Pentru rezolvarea problemei transportului se poate aplica ...

metoda potentiala

Metoda multiplicatorului Lagrange

metoda Gauss

metoda dezorientarii

53. În sistemul de constrângeri al problemei generale de programare liniară...

54. În sistemul de constrângeri al problemei de programare liniară standard (simetrică) ...

numai inegalitățile pot fi prezente

pot fi prezente atât ecuaţiile cât şi inegalităţile

numai ecuațiile pot fi prezente

55. În sistemul de constrângeri al problemei de programare liniară canonică (de bază) ...

pot fi prezente doar ecuații (cu condiția ca variabilele să fie nenegative)

pot fi prezente doar inegalitățile (cu condiția ca variabilele să fie nenegative)

atât ecuațiile, cât și inegalitățile pot fi prezente (cu condiția ca variabilele să fie nenegative)

56. Problema programării liniare

F(NS 1, NS 2)= 2NS 1 + 7NS 2 → max,

2NS 1 + 3NS 2 ≤ 14,

NS 1 + NS 2 ≤ 8,

NS 1 ≥ 0, NS 2 ≥ 0.

inregistrat in...

formă standard (simetrică).

formă canonică (de bază).

forma verbala

57. Pentru a înregistra o sarcină

F(NS 1, NS 2)= 2NS 1 + 7NS 2 → max,

2NS 1 + 3NS 2 ≤ 14,

NS 1 + NS 2 ≤ 8,

NS 1 ≥ 0, NS 2 ≥ 0.

in forma canonica...

58. Pentru a înregistra o sarcină

F(NS 1, NS 2)= 2NS 1 + 7NS 2 → max,

2NS 1 + 3NS 2 ≤ 14,

NS 1 + NS 2 ≤ 8,

NS 1 + 4NS 2 ≥ 10,

NS 1 ≥ 0, NS 2 ≥ 0.

in forma canonica...

este necesar să se introducă trei variabile suplimentare nenegative

este necesar să se introducă două variabile suplimentare nenegative

este necesar să se introducă patru variabile suplimentare nenegative

59. Pentru a înregistra o sarcină

F(NS 1, NS 2)= 2NS 1 + 7NS 2 → max,

2NS 1 + 3NS 2 = 14,

NS 1 + NS 2 ≤ 8,

NS 1 + 4NS 2 ≥ 10,

NS 1 ≥ 0, NS 2 ≥ 0.

in forma canonica...

este necesar să se introducă două variabile suplimentare nenegative

este necesar să se introducă trei variabile suplimentare nenegative

este necesar să se introducă patru variabile suplimentare nenegative

este necesar să se introducă cinci variabile suplimentare nenegative

60. La rezolvarea problemelor de programare cu numere întregi, poate fi folosit...

metoda Gomori

Metoda multiplicatorului Lagrange

metoda Gauss

Metoda de aproximare Vogel

61. În centrul rezolvării problemelor prin metoda programării dinamice se află ...

Briciul lui Occam

principiul „dinte pentru dinte, ochi pentru ochi”

Principiul Heisenberg

62. O situație în care sunt implicate părți, ale căror interese sunt total sau parțial opuse, se numește...

(conflict, conflict, conflict, conflict)

63. Un conflict real sau formal în care există cel puțin doi participanți (jucători), fiecare dintre care se străduiește să-și atingă propriile obiective, se numește ...

(joc, joc)

64. Acțiunile permise ale fiecărui jucător, care vizează atingerea unui anumit scop, se numesc ...

(reguli de joc, reguli de joc)

65. Evaluarea cantitativă a rezultatelor jocului se numește ...

(prin plată, plată, plată)

66. Dacă doar două părți (două persoane) participă la joc, atunci jocul se numește ...

(dublu, dublu, dublu, dublu)

67. Dacă într-un joc de dublu suma plăților este egală cu zero, adică pierderea unui jucător este egală cu câștigul celuilalt, atunci jocul se numește joc ...

(suma zero)

68. O descriere fără ambiguitate a alegerii jucătorului în fiecare dintre posibilele situații în care trebuie să facă o mișcare personală se numește ..

(strategie de jucător, strategie de jucător, strategie, strategie)

69. Dacă, cu repetări multiple ale jocului, strategia oferă jucătorului câștigul mediu maxim posibil (pierderea medie minimă posibilă), atunci o astfel de strategie se numește ...

(optim, optim, strategie optimă, strategie optimă)

70. Fie a prețul scăzut și b prețul ridicat al unui joc de dublu cu sumă zero. Atunci afirmația este adevărată...

71. Fie a prețul scăzut și b prețul ridicat al unui joc de dublu cu sumă zero. Dacă a = b = v, atunci numărul v se numește...

cu costul jocului

punct de echilibru

strategie optimă

strategie mixtă

72. Fie a prețul scăzut și b prețul ridicat al unui joc de dublu cu sumă zero. Dacă a = b, atunci jocul se numește...

joc cu puncte de șa

conflict insolubil

un joc fără reguli

73. Un vector, fiecare dintre componentele căruia arată frecvența relativă a utilizării de către jucător a strategiei pure corespunzătoare, se numește ...

strategie mixtă

vector de direcție

vector normal

gradient

74. Prețul mai mic al jocului matrice, dat de matricea de plată, este egal cu ...

Mai mult preț de jos

egal cu prețul de jos

nu exista

81. Un joc de matrice dat de o matrice de profit, ...

are un punct de șa

nu are punct de șa

nu pereche

82. Prețul jocului, dat de matricea plăților, este ...

83. Un joc de matrice dat de o matrice de profit ...

este pereche

are un punct de șa

nu pereche

84. Jocul de duble cu sumă zero, dat de matricea sa de profit, poate fi redus la...

problema de programare liniara

problema de programare neliniară

problema de programare liniara intregi

problema clasica de optimizare

85. Prețul mai mic al jocului matrice dat de matricea de plată este...

Mai mult preț de jos

egal cu prețul de jos

nu exista

92. Un joc de matrice dat de o matrice de profit ...

nu are punct de șa

are un punct de șa

nu pereche

93. Prețul jocului, dat de matricea de plată, este în ...

94. Dacă în fluxul de evenimente evenimentele se succed la intervale de timp predeterminate și strict definite, atunci un astfel de flux se numește ...

regulat

organizat

95. Dacă probabilitatea ca orice număr de evenimente să se încadreze într-un interval de timp depinde numai de lungimea acestui interval și nu depinde de cât de departe este situat acest interval de la începutul timpului, atunci fluxul corespunzător de evenimente se numește:

staționar

curge fara consecinte

cel mai simplu

Poisson

96. Dacă numărul de evenimente care se încadrează pe unul dintre intervalele de timp alese arbitrar nu depinde de numărul de evenimente care se încadrează pe un alt interval de timp, de asemenea, ales arbitrar, cu condiția ca aceste intervale să nu se intersecteze, atunci fluxul de evenimente corespunzător se numește ...

curge fara consecinte

regulat

indicativ

normal

97. Dacă probabilitatea ca două sau mai multe evenimente să lovească simultan un interval de timp foarte scurt este neglijabilă în comparație cu probabilitatea de a atinge un singur eveniment, atunci fluxul corespunzător de evenimente se numește...

comun

extraordinar

normal

Poisson

98. Dacă fluxul de evenimente posedă simultan proprietățile de staționaritate, ordinaritate și absența consecințelor, atunci se numește:

cel mai simplu (Poisson)

normal

99. Un sistem cu un singur canal cu defecțiuni este o stație zilnică de service pentru spălătorie auto. Aplicația - o mașină care a sosit în momentul în care postul este ocupat - primește o refuz de serviciu. Debitul mașinii λ = 1,0 (mașină pe oră). Durata medie de service este de 1,8 ore. Fluxul mașinii și fluxul serviciului sunt cele mai simple. Apoi, în starea de echilibru, debitul relativ q este egal...

100. Un sistem monocanal cu defecțiuni este o stație zilnică de service pentru spălătorie auto. Aplicația - o mașină care a sosit în momentul în care postul este ocupat - primește o refuz de serviciu. Debitul mașinii λ = 1,0 (mașină pe oră). Durata medie de service este de 1,8 ore. Fluxul mașinii și fluxul serviciului sunt cele mai simple. Apoi, în starea de echilibru, procentul de mașini care primesc o refuz de serviciu este ...

Formularea generală a problemei de programare liniară (LPP). Exemple de LPP

Programarea liniară este o ramură a matematicii care studiază metode de rezolvare a problemelor extreme, care se caracterizează printr-o relație liniară între variabile și un criteriu liniar de optimitate. Câteva cuvinte despre termenul de programare liniară. Este nevoie de o înțelegere corectă. În acest caz, programarea înseamnă, desigur, scrierea de programe de calculator. Programarea aici ar trebui interpretată ca planificare, formarea de planuri, dezvoltarea unui program de acțiune. Problemele matematice ale programării liniare includ studiul situațiilor specifice de producție și economice, care într-o formă sau alta sunt interpretate ca probleme de utilizare optimă a resurselor limitate. Gama de sarcini care pot fi rezolvate folosind metode de programare liniară este destul de largă. Acesta este, de exemplu:

• - problema utilizării optime a resurselor în planificarea producţiei;
• - problema amestecurilor (planificarea compozitiei produselor);
• - problema gasirii combinatiei optime a diverselor tipuri de produse pentru depozitarea in depozite (gestionarea stocurilor sau "problema rucsacului");
• - sarcini de transport (analiza locației întreprinderii, deplasarea mărfurilor). Programarea liniară este cea mai dezvoltată și utilizată ramură a programării matematice (în plus, aceasta include: programare întregă, dinamică, neliniară, parametrică). Acest lucru se datorează următoarelor:
• - modelele matematice ale unui număr mare de probleme economice sunt liniare în raport cu variabilele căutate;
• - acest tip de problemă este în prezent cea mai studiată. Pentru el s-au dezvoltat metode speciale cu ajutorul cărora se rezolvă aceste sarcini și programele de calculator corespunzătoare;
• - multe probleme de programare liniara, rezolvate, si-au gasit o larga aplicatie;
• - unele probleme care în formularea originală nu sunt liniare, după o serie de restricții și ipoteze suplimentare pot deveni liniare sau pot fi reduse la o astfel de formă încât să poată fi rezolvate prin metode de programare liniară. Modelul economic și matematic al oricărei probleme de programare liniară include: o funcție obiectiv, a cărei valoare optimă (maxim sau minim) trebuie găsită; restricții sub forma unui sistem de ecuații liniare sau inegalități; cerinţa de non-negativitate a variabilelor. În termeni generali, modelul este scris după cum urmează:
• - funcție obiectivă:

C1x1 + c2x2 + ... + cnxn> max (min); - restricții:

a11x1 + a12x2 + ... + a1nxn (? =?) b1,

a21x1 + a22x2 + ... + a2nxn (? =?) b2

am1x1 + am2x2 + ... + amnxn (? =?) bm;

Cerință de non-negativitate:

În acest caz, aij, bi, cj () sunt date constante. Problema este de a găsi valoarea optimă a funcției (2.1) supusă constrângerilor (2.2) și (2.3). Sistemul de constrângeri (2.2) se numește constrângeri funcționale ale problemei, iar constrângerile (2.3) sunt numite directe. Un vector care satisface constrângerile (2.2) și (2.3) se numește soluție fezabilă (plan) a problemei de programare liniară. Proiectul în care funcția (2.1) își atinge valoarea maximă (minimă) se numește optim.

Mai jos sunt exemple de unele probleme tipice rezolvate folosind metode de programare liniară. Astfel de sarcini au un real conținut economic. Acum le vom formula doar în termeni de LPP și vom lua în considerare metodele de rezolvare a unor astfel de probleme mai jos.

1. Problema utilizării optime a resurselor în planificarea producţiei. Sensul general al sarcinilor acestei clase este următorul. Întreprinderea produce n produse diferite. Producția lor necesită m diferite tipuri de resurse (materii prime, materiale, timp de muncă etc.). Resursele sunt limitate, rezervele lor în perioada de planificare sunt, respectiv, b1, b2, ..., bm unități convenționale. Sunt cunoscuți și coeficienții tehnologici aij, care arată câte unități din i-a resursă sunt necesare pentru a produce o unitate de al j-lea tip de produs (). Profitul primit de întreprindere din vânzarea produsului de tip j-lea este egal cu cj. În perioada de planificare, valorile aij, bi și cj rămân constante. Este necesar să se întocmească un astfel de plan de producție, în implementarea căruia profitul întreprinderii ar fi cel mai mare. Mai jos este un exemplu simplu de sarcină din această clasă.

Compania este specializată în producția de bețe de hochei și seturi de șah. Fiecare club generează 2 dolari în profit pentru companie și 4 dolari pentru fiecare set de șah. Este nevoie de patru ore pentru a face un club în Site-ul A și două ore în Site-ul B. Un set de șah este realizat cu șase ore în Site-ul A, șase ore în Site-ul B și o oră în Site-ul C. Capacitatea de producție disponibilă în Site-ul A este 120 Nm. - ore pe zi, secțiunea B - 72 n ore și secțiunea C - 10 n ore. Câte cluburi și seturi de șah ar trebui să producă zilnic o companie pentru a maximiza profiturile?

Condițiile pentru problemele acestei clase sunt adesea prezentate sub formă de tabel (vezi Tabelul 2.1).

În această condiție, formulăm o problemă de programare liniară. Să desemnăm: x1 - numărul de bețe de hochei produse zilnic, x2 - numărul de seturi de șah produse zilnic. Formularea ZLP:

4x1 + 6x2? 120,

Să subliniem că fiecare inegalitate din sistemul de constrângeri funcționale corespunde în acest caz unuia sau altuia loc de producție și anume: primul locului A, al doilea locului B și al treilea locului C.

Sistemul de variabile în problema optimizării structurii suprafețelor însămânțate, ținând cont de rotațiile culturilor