Dacă trebuie să rezolvați o problemă de programare liniară folosind tabele simplex, atunci serviciul nostru online vă va fi de mare ajutor. Metoda simplex implică o enumerare secvențială a tuturor vârfurilor intervalului de valori admisibile pentru a găsi vârful în care funcția ia o valoare extremă. În prima etapă, se găsește o soluție, care se îmbunătățește la fiecare pas ulterior. Această soluție se numește de bază. Iată o secvență de acțiuni atunci când rezolvați o problemă de programare liniară folosind metoda simplex:
Primul pas. În tabelul compilat, în primul rând, trebuie să vă uitați la coloana cu membri liberi. Dacă există elemente negative în el, atunci este necesar să treceți la a doua etapă, dacă nu, atunci la a cincea.
Al doilea pas. La a doua etapă, este necesar să se decidă ce variabilă să se excludă din bază și care să includă, pentru a recalcula tabelul simplex. Pentru a face acest lucru, căutați prin coloana cu membri liberi și găsiți un element negativ în ea. Linia cu un element negativ va fi numită linie de conducere. În el găsim elementul negativ maxim în valoare absolută, coloana corespunzătoare - adeptul. Dacă există valori negative printre membrii liberi, dar nu în rândul corespunzător, atunci un astfel de tabel nu va avea soluții. Schimbarea în rândul principal, cel din coloana membru liber este exclus din bază, iar variabila corespunzătoare coloanei principale este inclusă în bază.
Tabelul 1.
| variabile de bază | Membri liberi în constrângeri | Variabile nonbaze | |||||
| x 1 | x 2 | ... | x l | ... | x n | ||
| x n + 1 | b 1 | un 11 | un 12 | ... | un 1l | ... | un 1n |
| x n + 2 | b 2 | un 21 | un 22 | ... | un 2l | ... | un 2n |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| x n + r | b2 | un r1 | un r2 | ... | un rl | ... | a rn |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| x n + m | b m | un m1 | un m2 | ... | un ml | ... | un mn |
| F (x) max | F 0 | -c 1 | -c 2 | ... | -c 1 | ... | -c n |
Pasul trei. La al treilea pas, recalculăm întregul tabel simplex folosind formule speciale, aceste formule pot fi văzute folosind.
Al patrulea pas. Dacă, după recalculare, elemente negative rămân în coloana de membri liberi, atunci treceți la primul pas, dacă nu există, atunci la al cincilea.
Al cincilea pas. Dacă ați ajuns la al cincilea pas, atunci ați găsit o soluție acceptabilă. Cu toate acestea, acest lucru nu înseamnă că este optim. Va fi optim numai dacă toate elementele din rândul F sunt pozitive. Dacă nu este cazul, atunci este necesară îmbunătățirea soluției, pentru care găsim rândul și coloana de început pentru următoarea recalculare conform următorului algoritm. Inițial, găsim numărul minim negativ în linia F, excluzând valoarea funcției. Coloana cu acest număr va fi prima. Pentru a găsi rândul de început, găsim raportul dintre membrul liber corespunzător și elementul din coloana principală, cu condiția ca acestea să fie pozitive. Relația minimă vă va permite să definiți rândul de început. Recalculam din nou tabelul folosind formulele, i.e. treceți la pasul 3.
Metoda grafică este destul de simplă și intuitivă pentru rezolvarea problemelor LP cu două variabile. Se bazeaza pe geometric reprezentarea soluţiilor fezabile şi CF a problemei.
Fiecare dintre inegalitățile problemei LP se definește pe planul de coordonate (NS 1 ,NS 2 ) unele semiplane (Fig. 1), iar sistemul de inegalități în ansamblu este intersecția planurilor corespunzătoare. Mulțimea punctelor de intersecție a acestor semiplane se numește zona de admisiedecizii(ODR). SDT reprezintă întotdeauna convex figura, adică care are urmatoarea proprietate: daca doua puncte A si B apartin acestei figuri, atunci ii apartine intregul segment AB. ODR poate fi reprezentat grafic printr-un poligon convex, o regiune poligonală convexă nemărginită, un segment, o rază, un punct. În cazul inconsecvenței sistemului de constrângeri, problema SDT este o mulțime goală.
Notă № 1. Toate cele de mai sus se aplică și în cazul în care sistemul de constrângeri (1.1) include egalități, deoarece orice egalitate
a il x 1 + a i 2 x 2 = b
poate fi reprezentat ca un sistem de două inegalități (Fig. 1)
A i 2 x 2<Ь 1э +a i 2 x 2 >B j.
CF L (x) = c1x1 + c2x2 cu o valoare fixă L (x) = L definește o dreaptă c1x1 pe plan + c2x2 = L. Schimbând valorile lui L, obținem o familie de drepte paralele, numite linii de nivel.
Acest lucru se datorează faptului că o modificare a valorii lui L va presupune o modificare numai a lungimii segmentului tăiat de linia de nivel pe axa x2 (ordonată inițială) și a pantei dreptei tgа = - va rămâne constantă (Fig. 1).
Prin urmare, pentru a o rezolva, va fi suficient să construiți una dintre liniile de nivel, alegând în mod arbitrar valoarea lui L.
Vectorul C = (c1; c2) cu coordonatele din coeficienții CF la x1 și x2 este perpendicular pe fiecare dintre liniile de nivel (vezi Fig. 1). Direcţievectorul С coincide cu direcție crește CF, care este un punct important pentru rezolvarea problemelor. Direcţie diminuându-se CF opusuldirecția vectorului C.
Esența metodei grafice este următoarea. În direcția (contra direcției) vectorului C din ODR, căutarea punctului optim X = (x1; x2 ). Punctul optim este punctul prin care trece linia de nivel L max (L min), corespunzătoare celei mai mari (mai mici) valori a funcției L (x). Soluția optimă este întotdeauna situată la granița ODR, de exemplu, la ultimul vârf al poligonului ODR, prin care trece linia țintă, sau pe toată latura sa.
Când se caută o soluție optimă pentru problemele LP, sunt posibile următoarele situații: există o soluție unică a problemei; există un număr infinit de soluții (opțiune alternativă); CF nu este limitat; zona soluțiilor admisibile este singurul punct; sarcina nu are soluții.
Zona valabilă - semiplan
Poza 1
1.2. Metodologie de rezolvare a problemelor LP prin metoda grafică
I. În constrângerile problemei, înlocuiți semnele inegalităților cu semne ale egalităților exacte și construiți dreptele corespunzătoare.
II. Găsiți și umbriți semiplanurile rezolvate de fiecare dintre constrângerile de inegalitate din problemă. Pentru a face acest lucru, înlocuiți coordonatele unui punct [de exemplu, (0; 0)] într-o inegalitate specifică și verificați adevărul inegalității rezultate.
Dacă inegalitatea este adevărată, atunci este necesar să umbriți semiplanul care conține punctul dat; in caz contrar (inegalitatea este falsă) este necesară umbrirea semiplanului care nu conține punctul dat.
Din moment ce x1 și x2 trebuie să fie nenegative, atunci valorile lor permise vor fi întotdeauna deasupra axei x 1 și în dreapta axei x2, adică. în cadranul 1.
Constrângerile de egalitate permit numai acele puncte care se află pe linia corespunzătoare, așa că selectați astfel de linii pe grafic.
Definiți un IDT ca parte a avionului care aparține tuturor zonelor permise în același timp și selectați-l. În absența unui IDT, sarcina nu are solutii, despre care face concluzia potrivită.
Dacă ODR nu este un set gol, atunci construiți linia țintă, de exemplu. oricare dintre liniile de nivel cu 1 x 1 + cu 2 x 2 = L, unde L este un număr arbitrar, de exemplu, un multiplu de 1 iar cu 2, i.e. convenabil pentru efectuarea calculelor. Metoda de construcție este similară cu construcția constrângerilor directe.
V. Construiți vectorul C = (c 1, c 2), care începe în punctul (0; 0), se termină în punctul (c 1, c 2). Dacă linia țintă și vectorul C sunt construite corect, atunci vor fi perpendicular.
Vi. Când căutați DF maxim, mutați linia țintă in directia vector C, când se caută min CF - împotriva direcției vectorul C. Ultimul de-a lungul mișcării, vârful ODR va fi punctul maxim sau min al CF. Dacă un astfel de punct (puncte) nu există, atunci trageți o concluzie despre nelimitarea CF pe multe planuri sus (când se caută cecul) sau dedesubt (când se caută min).
Determinați coordonatele punctului max (min) DF X = (x1 *; x2 * ) și calculați valoarea CF l (x *). Pentru a calcula coordonatele punctului optim X *, rezolvați sistemul de ecuații ale dreptelor la intersecția cărora se află X *.
Problema 1
Să găsim soluția optimă a problemei, al cărei model matematic are forma
L (X) = 3x 1 + 2x 2 → max
x 1 + 2x 2< 6, (1)
2x 1 + x 2< 8, (2)
X 1 + x 2<1, (3)
x 2< 2, (4)
x 1> 0, x 2> 0.
Să construim linii de constrângeri, pentru care să calculăm coordonatele punctelor de intersecție ale acestor drepte cu axele de coordonate (Fig. 2).
x 1 + 2x 2 = 6, (1)
2x1 + x2 = 8, (2)
(1) x1 = 0, x1 = 6, x2 = 3, x2 = 0,
(2) x1 = 0, x1 = 4, x2 = 8, x2 = 0,
(3) x1 = 0, x1 = -1, x2 = 1, x2 = 0,
Linia dreaptă (4) trece prin punctul x 2 = 2 paralel cu axa L (X).
Orez. 2. Rezolvarea grafică a problemei
Să definim ODR. De exemplu, înlocuiți punctul (0; 0) în constrângerea inițială (3), obținem 0< 1, что является истинным неравенством, поэтому стрелкой (или штрихованием) обозначим полуплоскость, conținând punctul (0; 0), adică situată în dreapta și sub linia dreaptă (3). În mod similar, definim semiplanurile admisibile pentru constrângerile rămase și le indicăm cu săgeți la constrângerile directe corespunzătoare (Fig. 2). O zonă comună permisă de toate restricțiile, de ex. ODR este poligonul ABCDEF.
Linia țintă poate fi trasată conform ecuației
Construim vectorul C de la punctul (0; 0) la punctul (3; 2). Punctul E este ultimul vârf al poligonului soluțiilor fezabile ABCDEF, prin care trece linia țintă, mișcându-se către vector C. Prin urmare, E este punctul maxim al CF. Să determinăm coordonatele punctului E din sistemul de ecuații ale constrângerilor directe (1) și (2)
X1 + 2x 2 = 6, (1) x1 = 10/3 = 3 1/3, x2 = 4/3 = 1 1/3
2 X1 + x 2 = 8, (2) E 3 1/3; 1 1/3
Valoarea maximă a CF este L (E) = 3 * 10/3 + 2 * 4/3 = 12 2/3
Să luăm mai întâi în considerare cel mai simplu caz, când exact două variabile sunt incluse în LPP:
Fiecare dintre inegalitățile (a) - (b) ale sistemului de constrângeri din problema (3.8) definește geometric un semiplan cu linii de limită, X 1 = 0 și respectiv X 2 = 0. Fiecare dintre liniile de limită împarte planul x 1 Ox 2 în două semiplane. Toate soluțiile inegalității inițiale se află într-unul dintre semiplanurile formate (toate punctele semiplanului) și, prin urmare, atunci când coordonatele oricăruia dintre punctele sale sunt substituite în inegalitatea corespunzătoare, o transformă într-o adevărată identitate. . Ținând cont de acest lucru, se determină semiplanul în care se află soluțiile inegalității, adică. prin alegerea oricărui punct din orice semiplan și substituind coordonatele acestuia în inegalitatea corespunzătoare. Dacă inegalitatea este valabilă pentru un punct dat, atunci este valabilă pentru orice alt punct din același semiplan. În caz contrar, soluțiile inegalității se află într-un alt semiplan.
Dacă sistemul de inegalități (a) - (b) este consecvent, atunci domeniul soluțiilor sale este mulțimea de puncte aparținând tuturor semiplanurilor indicate. Deoarece mulțimea punctelor de intersecție a acestor semiplane este convexă, domeniul soluțiilor fezabile la problema (3.8) este o mulțime convexă, care se numește poligon de soluții (termenul introdus anterior „politop de soluții” este de obicei folosit dacă n 3). Laturile acestui poligon se află pe linii drepte, ale căror ecuații sunt obținute din sistemul original de constrângeri prin înlocuirea semnelor de inegalitate cu semne de egalități exacte.
Astfel, LPP inițial constă în găsirea unui punct al poligonului de decizie la care funcția obiectiv F ia valoarea maximă (minimă).
Acest punct există atunci când poligonul soluție nu este gol și funcția obiectiv este mărginită de sus pe el. În aceste condiții, la unul dintre vârfurile poligonului de decizie, funcția obiectiv își ia valoarea maximă. Pentru a determina acest vârf, se construiește o linie de nivel L: c 1 x 1 + c 2 x 2 = h (unde h este o constantă), perpendiculară pe vectorul gradient și care trece prin poligonul soluției și mutați-l paralel de-a lungul gradientului vector până când, până când trece prin ultimul său punct comun de intersecție cu poligonul de soluții (când se construiește un vector gradient, se așează un punct (c 1; c 2) în planul x 1 Ox 2 și se trasează un segment direcționat la acesta de la originea coordonatelor). Coordonatele punctului specificat determină planul optim pentru această sarcină.
Rezumând toate cele de mai sus, prezentăm un algoritm pentru metoda grafică de rezolvare a LPP.
Algoritmul metodei grafice de rezolvare a LPP
1. Construiți un poligon de soluții date de sistemul de constrângeri al LPP inițial.
2. Dacă poligonul de soluții construit este o mulțime goală, atunci LPP inițial nu are soluții. În caz contrar, construiți un vector-gradient și trasați o linie arbitrară de nivel L, deplasându-se care, la rezolvarea problemei la maxim în direcția vectorului (sau în sens invers pentru problema la minim), determină punctul extrem. a poligonului soluție, unde se realizează maximul (minimul) funcției obiectiv a problemei...
3. Calculați coordonatele punctului optim găsit prin rezolvarea sistemului de ecuații a două linii de frontieră care se intersectează în acesta.
4. Înlocuind soluția optimă găsită în funcția obiectiv a problemei, calculați valoarea optimă a acesteia, adică:.
La construirea grafică a mulțimii soluțiilor admisibile ale LPP (poligonul soluției), sunt posibile următoarele situații.
Modelarea matematică în cercetarea operațională este, pe de o parte, un proces foarte important și complex, iar pe de altă parte, practic nu este susceptibilă de formalizare științifică. De remarcat faptul că încercările repetate de a evidenția principiile generale de creare a modelelor matematice au condus fie la declararea unor recomandări cu caracter foarte general, greu de aplicat la rezolvarea unor probleme specifice, fie, dimpotrivă, la apariția unor rețete care sunt efectiv aplicabile doar la o gamă restrânsă de probleme. Prin urmare, familiarizarea cu tehnica modelării matematice pe exemple specifice pare a fi mai utilă.
Problemele de programare liniară pot fi rezolvate prin următoarele metode:
algoritmul lui Floyd;
algoritmul lui Dijkstra pe grafice;
metoda grafica;
metoda tabelului simplex etc.
Algoritm pentru rezolvarea problemelor de programare liniară prin metoda lui Dijkstra pe grafice.
În cea mai simplă implementare, puteți folosi o matrice de numere pentru a stoca numerele d [i] și o matrice de variabile booleene pentru a stoca apartenența unui element la mulțimea U.
La începutul algoritmului, distanța pentru vârful inițial este setată egală cu zero și toate celelalte distanțe sunt umplute cu un număr pozitiv mare (mai mare decât calea maximă posibilă din grafic). Matricea flags este umplută cu zerouri. Apoi începe bucla principală.
La fiecare pas al ciclului, este necesar să se găsească vârful U cu distanța minimă și steagul egal cu zero. Apoi trebuie să setăm steagul din el la 1 și să verificăm toate vârfurile adiacente U. Dacă distanța este mai mare decât suma distanței până la vârful curent și lungimea muchiei, atunci este necesar să o micșorăm . Ciclul se termină când steagurile tuturor nodurilor devin egale cu 1, sau când toate nodurile au un steag de 0. Acest din urmă caz este posibil dacă și numai dacă graficul G nu este conectat.
O metodă pentru rezolvarea problemelor de programare liniară folosind o metodă grafică.
Metoda grafică de rezolvare a problemelor de programare liniară se bazează pe interpretarea geometrică a problemelor de programare liniară și este utilizată în principal în rezolvarea problemelor în spațiul bidimensional și doar a unor probleme în spațiul tridimensional, deoarece este destul de dificil să se construiască un poliedru de soluții, care se formează ca urmare a intersecției semispațiilor. În general, este imposibil să descrii grafic problema unui spațiu cu dimensiuni mai mari de trei.
Să fie dată problema de programare liniară într-un spațiu bidimensional, adică constrângerile conțin două variabile.
Valoarea minimă a funcției este determinată de formula (1).
(1)
Restricțiile sunt reprezentate prin formulele (2) și (3).
(2)
(3)
Fie sistemul (2) în condiția (3) să fie consecvent. Fiecare dintre inegalitățile din sistemele (2) și (3) definește un semiplan cu linii de limită reprezentate prin formula (4):
Funcția liniară (1) la valori fixe ale lui Z este ecuația unei linii drepte: 
Este necesar să se construiască poligonul de soluții ale sistemului de constrângeri (2) și graficul funcției liniare (1) la Z = 0. Atunci problema de programare liniară setată poate fi interpretată după cum urmează:
Aflați punctul poligonului soluție în care linia 
cel de referinţă şi funcţia Z în acelaşi timp atinge un minim.
Valorile 
scăderea în direcția vectorului 
, prin urmare, dreapta Z = 0 trebuie deplasată paralel cu ea însăși în direcția vectorului N.
Dacă poligonul soluție este mărginit, atunci linia dreaptă devine de două ori linia de sprijin față de poligonul soluție (în punctele B și E), cu valoarea minimă în punctul E. Coordonatele punctului 
trebuie găsit prin rezolvarea sistemului de ecuații pentru dreptele DE și EF.
Dacă poligonul soluție este o regiune poligonală nemărginită, atunci sunt posibile două cazuri.
Cazul 1. Direct 
deplasându-se în direcția vectorului N sau opusă acestuia, intersectează constant poligonul soluție și în niciun moment nu este o referință la acesta. În acest caz, funcția liniară nu este mărginită pe poligonul soluție nici de sus, nici de jos.
Cazul 2. O linie dreaptă, în mișcare, devine totuși un suport relativ la poligonul soluție. Apoi, în funcție de tipul regiunii, funcția liniară poate fi mărginită de sus și nemărginită de jos, mărginită de jos și nemărginită de sus sau mărginită atât de jos, cât și de sus.
Pentru rezolvarea acestei probleme s-a ales cea mai cunoscută și utilizată pe scară largă în practică pentru rezolvarea problemelor de programare liniară este metoda simplex. În ciuda faptului că metoda simplex este un algoritm destul de eficient care a dat rezultate bune în rezolvarea problemelor aplicate de programare liniară, este un algoritm cu complexitate exponențială.
Metoda simplex a problemelor de programare liniară se bazează pe trecerea de la un plan de bază la altul, în care valoarea funcției obiectiv crește sau scade.
Înainte de alcătuirea unui tabel simplex, sarcina trebuie transformată, sistemul de restricții adus la o formă de bază admisibilă, cu ajutorul căreia variabilele de bază trebuie excluse din funcția obiectiv, așa cum se arată în Figura 1.
Figura 1 - Transformarea inițială a sistemului de restricții
Aici, pentru caracterul precis al notației, se presupune că variabilele X1, X2, ..., Xr pot fi luate ca variabile de bază și că b1, b2, ..., br ≥ 0 (soluția de bază corespunzătoare este referința unu).
Pentru a compila un tabel simplex în toate egalitățile din enunțul problemei, termenii care conțin variabilele sunt transferați în partea stângă, cei liberi sunt lăsați în dreapta, adică. problema este scrisă sub forma unui sistem de egalități, așa cum se arată în figura 2.
Figura 2 - Transformarea sistemului de inegalități
Algoritmul pentru trecerea la următorul tabel este următorul:
se scanează ultimul rând din tabelul (index) iar dintre coeficienții acestui rând (excluzând coloana de membri liberi) se selectează cel mai mic număr negativ la găsirea max, sau cel mai mare număr pozitiv la găsirea min. Dacă nu există, atunci soluția de bază originală este optimă și acest tabel este ultimul;
coloana tabelului este scanată corespunzător coeficientului negativ (pozitiv) selectat în ultimul rând - coloana cheie, iar coeficienții pozitivi sunt selectați în această coloană. Dacă nu există, atunci funcția obiectiv este nelimitată pe intervalul de valori admisibile ale variabilelor și problema nu are soluții;
dintre coeficienții selectați ai coloanei, se selectează cel pentru care valoarea absolută a raportului dintre membrul liber corespunzător (situat în coloana membrelor libere) și acest element este minimă. Acest coeficient se numește rezoluție, iar linia în care se află este cheia;
în viitor, variabila de bază corespunzătoare rândului elementului de autorizare trebuie convertită în categoria celor libere, iar variabila liberă corespunzătoare coloanei elementului de autorizare trebuie introdusă în numărul de elemente de bază. Se construiește un nou tabel care conține noile nume ale variabilelor de bază:
vom împărți fiecare element al liniei cheie (excluzând coloana de membri liberi) într-un element de rezoluție și vom scrie valorile obținute în linia cu variabila de bază modificată a noului tabel simplex.
rândul elementului de rezolvare este împărțit la acest element și șirul rezultat este scris în noul tabel în același loc.
în noul tabel, toate elementele coloanei cheie = 0, cu excepția coloanei de tăiere, este întotdeauna egală cu 1.
coloana cu 0 în rândul de chei va fi aceeași în noul tabel.
un rând care are un 0 în coloana cheie va fi același în noul tabel.
în restul celulelor noului tabel se scrie rezultatul transformării elementelor vechiului tabel, așa cum se arată în Figura 3.
Figura 3 - Întocmirea unui nou element într-un tabel simplex
Ca urmare, se obține un nou tabel simplex care corespunde noii soluții de bază.
Acum ar trebui să priviți prin linia funcției obiectiv (indice), dacă nu conține valori negative (în problema găsirii valorii maxime) sau pozitive (în problema găsirii valorii minime), cu excepția unul în picioare (coloană liberă), atunci înseamnă că soluția optimă a primit. În caz contrar, mergeți la un nou tabel simplex folosind algoritmul descris mai sus.
Pentru a rezolva problema acestui lucru de curs, a fost aleasă direcția problemei pentru repartizarea optimă a fondurilor la întreprindere. Planul optim sau soluția optimă pentru o problemă de programare liniară este un plan în care valoarea țintă va crește (scădea).
În urma analizei informațiilor colectate, a fost întocmită o sarcină de programare liniară pentru atelierul Nr. 8 de la OJSC NefAZ Pe transportorul de vopsea, pe care sunt vopsite piesele. Este necesar să pictați numărul optim de piese pe schimb de lucru pentru a maximiza profitul.
Pentru a rezolva în continuare problema, este necesar să se formuleze problema și modelul matematic al problemei.
Programarea liniară folosește o metodă grafică pentru a defini mulțimi convexe (poliedru de soluție). Dacă problema principală de programare liniară are un design optim, atunci funcția obiectiv ia o valoare la unul dintre vârfurile poliedrului de decizie (vezi figura).
Scopul serviciului... Cu ajutorul acestui serviciu este posibilă rezolvarea problemei de programare liniară prin metoda geometrică în modul online, precum și obținerea unei soluții la problema duală (pentru evaluarea optimității utilizării resurselor). În plus, un șablon de soluție este creat în Excel.
Instruire. Selectați numărul de linii (numărul de constrângeri). Dacă numărul de variabile este mai mare de două, este necesar să aduceți sistemul la SZLP (vezi și exemplul nr. 2). Dacă constrângerea este dublă, de exemplu, 1 ≤ x 1 ≤ 4, atunci este împărțită în două: x 1 ≥ 1, x 1 ≤ 4 (adică numărul de linii este crescut cu 1).
De asemenea, puteți construi o regiune de soluție fezabilă (ADR) folosind acest serviciu.
Următoarele sunt, de asemenea, utilizate cu acest calculator:
Metoda simplex pentru rezolvarea LPP
Rezolvarea problemei de transport
Soluție de joc Matrix
Folosind serviciul online, puteți determina prețul unui joc matrice (limitele inferioare și superioare), puteți verifica prezența unui punct de șa, puteți găsi o soluție la o strategie mixtă folosind următoarele metode: minimax, metoda simplex, grafică (geometrică) metoda, metoda lui Brown.
Extremul unei funcții a două variabile
Calcularea limitelor
Rezolvarea problemei de programare liniara prin metoda grafica include urmatorii pasi:
- Pe planul X 1 0X 2 sunt trasate linii drepte.
- Se determină semiplanurile.
- Determinați poligonul soluției;
- Construiți un vector N (c 1, c 2), care indică direcția funcției obiectiv;
- Mutați funcția obiectiv direct c 1 x 2 + c 2 x 2= 0 în direcția vectorului N până la punctul extrem al poligonului soluție.
- Se calculează coordonatele punctului și valoarea funcției obiectiv în acest punct.
Un exemplu. Compania produce două tipuri de produse - P1 și P2. Pentru producerea produselor se folosesc două tipuri de materii prime - C1 și C2. Pretul cu ridicata al unei unitati de productie este egal cu: 5 UC. pentru P1 și 4 unități pentru P2. Consumul de materii prime pe unitatea de producție de tip P1 și tip P2 este prezentat în tabel.
Tabel - Consumul de materii prime pentru productie
Este necesar să se definească:
Câte produse de fiecare tip ar trebui să producă compania pentru a maximiza veniturile din vânzările de produse?
- Formulați un model matematic al unei probleme de programare liniară.
- Rezolvați problema de programare liniară grafic (pentru două variabile).
Să formulăm un model matematic al problemei de programare liniară.
x 1 - producția de produse P1, unități.
x 2 - producția de produse P2, unități.
x 1, x 2 ≥ 0
Limitele resurselor
6x 1 + 4x 2 ≤ 24
x 1 + 2x 2 ≤ 6
Constrângerile cererii
x 1 +1 ≥ x 2
x 2 ≤ 2
Funcție obiectivă
5x 1 + 4x 2 → max
Apoi obținem următorul LPP:
6x 1 + 4x 2 ≤ 24
x 1 + 2x 2 ≤ 6
x 2 - x 1 ≤ 1
x 2 ≤ 2
x 1, x 2 ≥ 0
5x 1 + 4x 2 → max
Dacă numărul de variabile într-o problemă de programare liniară este mai mare de două, atunci problema este redusă preliminar la un LPP standard.
→ max sub constrângeri:
x 1 + x 2 + x 3 = 12
2x 1 - x 2 + x 4 = 8
- 2x 1 + 2x 2 + x 5 = 10
F (X) = 3x 1 - 2x 2 + 5x 3 - 4x 5
Trecerea la SZLP.
| 1 | 1 | 1 | 0 | 0 | 12 |
| 2 | -1 | 0 | 1 | 0 | 8 |
| -2 | 2 | 0 | 0 | 1 | 10 |
Să reducem sistemul la matricea unitară prin metoda transformărilor Jordan.
x 1 + x 2 + x 3 = 12
2x 1 - x 2 + x 4 = 8
- 2x 1 + 2x 2 + x 5 = 10
x 3 = - x 1 - x 2 +12
x 4 = - 2x 1 + x 2 +8
x 5 = 2x 1 - 2x 2 +10
sau
Sistemul de inegalități:
- x 1 - x 2 +12 ≥ 0
- 2x 1 + x 2 +8 ≥ 0
2x 1 - 2x 2 +10 ≥ 0
x 1 + x 2 ≤ 12
2x 1 - x 2 ≤ 8
- 2x 1 + 2x 2 ≤ 10
Caracteristici de rezolvare a problemelor de programare liniară folosind o metodă grafică
Exemplul #1. Notați problema într-o formă standard și rezolvați-o grafic.f = x 1 + 13x 2 -x 3 + 2x 4 + 3x 5
-x 2 + x 3 -x 5 = -3
x 1 -4x 2 + 3x 3 -x 4 + 2x 5 = 3
4x 2 -x 3 + x 4 -x 5 = 6
Din prima ecuație exprimăm x 5:
x 5 = -x 2 + x 3 +3
f = x 1 + 13x 2 -x 3 + 2x 4 +3 (-x 2 + x 3 +3)
x 1 -4x 2 + 3x 3 -x 4 +2 (-x 2 + x 3 +3) = 3
4x 2 -x 3 + x 4 - (- x 2 + x 3 +3) = 6
sau
f = x 1 + 10x 2 + 2x 3 + 2x 4 +9
x 1 -6x 2 + 5x 3 -x 4 = -3
5x 2 -2x 3 + x 4 = 9
Din a doua ecuație exprimăm x 4:
x 4 = 9-5x 2 + 2x 3
și înlocuiți în toate expresiile:
f = x 1 + 6x 3 +27
x 1 -x 2 + 3x 3 = 6
Luăm variabila x 2 ca o variabilă suplimentară și o înlocuim cu semnul „≥”:
f = x 1 + 6x 3 + 27
x 1 + 3x 3 ≥6
Exemplul nr. 2
x 1 + x 2 + x 3 = 12
2x 1 - x 2 + x 4 = 8
- 2x 1 + 2x 2 + x 5 = 10
F (X) = 3x 1 - 2x 2 + 5x 3 - 4x 5
Trecerea la SZLP.
Matricea extinsă a sistemului de constrângeri-egalități ale acestei probleme:
| 1 | 1 | 1 | 0 | 0 | 12 |
| 2 | -1 | 0 | 1 | 0 | 8 |
| -2 | 2 | 0 | 0 | 1 | 10 |
1. Puteți alege x 3 ca variabilă de bază.
2. Puteți alege x 4 ca variabilă de bază.
3. Puteți alege x 5 ca variabilă de bază.
Deoarece sistemul are o matrice unitară, luăm X = (3,4,5) ca variabile de bază.
Ecuațiile corespunzătoare sunt:
x 1 + x 2 + x 3 = 12
2x 1 - x 2 + x 4 = 8
- 2x 1 + 2x 2 + x 5 = 10
Să exprimăm variabilele de bază în termeni de restul:
x 3 = - x 1 - x 2 +12
x 4 = - 2x 1 + x 2 +8
x 5 = 2x 1 - 2x 2 +10
Să le substituim în funcția obiectiv:
F (X) = 3x 1 - 2x 2 + 5 (- x 1 - x 2 +12) - 4 (2x 1 - 2x 2 +10)
sau
F (X) = - 10x 1 + x 2 +20 → max
Sistemul de inegalități:
- x 1 - x 2 +12 ≥ 0
- 2x 1 + x 2 +8 ≥ 0
2x 1 - 2x 2 +10 ≥ 0
Aducem sistemul de inegalități în următoarea formă:
x 1 + x 2 ≤ 12
2x 1 - x 2 ≤ 8
- 2x 1 + 2x 2 ≤ 10
F (X) = - 10x 1 + x 2 +20 → max
Exemplul nr. 3. Creați un model matematic al unei probleme de programare liniară și găsiți o soluție într-un mod geometric.
- Întocmește un sistem de dependențe (inegalități) matematice și o funcție obiectiv.
- Desenați o interpretare geometrică a problemei.
- Găsiți soluția optimă.
- Verificare analitică.
- Determinați resursele esențiale și neesențiale și surplusurile acestora.
- Determinați valoarea funcției obiectiv.
- Calculați estimări determinate obiectiv.
- Întocmește raportul de stabilitate.
