Metoda simplex este. Rezolvarea problemei folosind metoda simplex

Această metodă este o metodă de enumerare intenționată a soluțiilor de referință la o problemă de programare liniară. Permite, într-un număr finit de pași, fie să se găsească o soluție optimă, fie să se stabilească că nu există o soluție optimă.

1. Indicați o metodă pentru găsirea soluției de referință optime
2. Indicați metoda de trecere de la o soluție de referință la alta, la care valoarea funcției obiectiv va fi mai apropiată de cea optimă, adică. indica o modalitate de a îmbunătăți soluția de referință
3. Stabiliți criterii care vă permit să opriți imediat căutarea soluțiilor de asistență la soluția optimă sau să trageți o concluzie despre absența unei soluții optime.

Algoritmul metodei simplex pentru rezolvarea problemelor de programare liniară

1. Aduceți problema în formă canonică
2. Găsiți soluția de suport inițială cu o „bază unitară” (dacă nu există o soluție de suport, atunci problema nu are o soluție din cauza incompatibilității sistemului de constrângeri)
3. Calculați estimări ale descompunerilor vectoriale pe baza soluției de referință și completați tabelul metodei simplex
4. Dacă criteriul de unicitate al soluției optime este îndeplinit, atunci soluția problemei se termină
5. Dacă este îndeplinită condiția existenței unui set de soluții optime, atunci toate soluțiile optime se găsesc prin enumerare simplă

Un exemplu de rezolvare a unei probleme folosind metoda simplex

Rezolvați problema folosind metoda simplex:

Soluţie:

Aducem problema în formă canonică.

Pentru a face acest lucru, introducem o variabilă suplimentară x 6 cu coeficient +1 în partea stângă a primei constrângeri de inegalitate. Variabila x 6 este inclusă în funcția obiectiv cu un coeficient de zero (adică nu este inclusă).

Primim:

Găsim soluția inițială de suport. Pentru a face acest lucru, echivalăm variabilele libere (nerezolvate) cu zero x1 = x2 = x3 = 0.

Primim soluție de referință X1 = (0,0,0,24,30,6) cu baza unitară B1 = (A4, A5, A6).

Noi calculăm estimări ale descompunerilor vectoriale condiții pe baza soluției de referință conform formulei:

Δ k = C b X k - c k

• C b = (c 1, c 2, ..., c m) - vector de coeficienți ai funcției obiectiv pentru variabilele de bază
• X k = (x 1k, x 2k, ..., x mk) - vector de expansiune a vectorului corespunzător A k în funcție de baza soluției de referință
• C k este coeficientul funcției obiectiv pentru variabila x k.

Estimările vectorilor incluși în bază sunt întotdeauna egale cu zero. Soluția de referință, coeficienții de expansiune și estimările expansiunilor vectorilor de condiție bazate pe soluția de referință sunt scrise în tabel simplex:

În partea de sus a tabelului, pentru ușurința calculului estimărilor, se scriu coeficienții funcției obiectiv. În prima coloană „B” se scriu vectorii incluși în baza soluției de referință. Ordinea în care acești vectori sunt scriși corespunde numărului de necunoscute permise în ecuațiile de constrângere. În a doua coloană a tabelului „C b” se scriu în aceeași ordine coeficienții funcției obiectiv pentru variabilele de bază. La locația corectă Coeficienții funcției obiectiv din coloana „C b” a estimării vectorilor unitari incluși în bază sunt întotdeauna egali cu zero.

În ultimul rând al tabelului cu estimări ale Δ k în coloana „A 0” sunt scrise valorile funcției obiectiv pe soluția de referință Z(X 1).

Soluția suport inițial nu este optimă, deoarece în problema maximă estimările Δ 1 = -2, Δ 3 = -9 pentru vectorii A 1 și A 3 sunt negative.

Conform teoremei de îmbunătățire a soluției suport, dacă într-o problemă de maxim cel puțin un vector are o estimare negativă, atunci puteți găsi o nouă soluție suport pe care valoarea funcției obiectiv va fi mai mare.

Să determinăm care dintre cei doi vectori va duce la o creștere mai mare a funcției obiectiv.

Incrementul functiei obiectiv se gaseste prin formula: .

Calculăm valorile parametrului θ 01 pentru prima și a treia coloană folosind formula:

Se obține θ 01 = 6 pentru l = 1, θ 03 = 3 pentru l = 1 (Tabelul 26.1).

Găsim incrementul funcției obiectiv la introducerea în bază a primului vector ΔZ 1 = - 6*(- 2) = 12, iar al treilea vector ΔZ 3 = - 3*(- 9) = 27.

În consecință, pentru o abordare mai rapidă a soluției optime, este necesar să se introducă vectorul A3 în baza soluției de referință în locul primului vector al bazei A6, deoarece minimul parametrului θ 03 este atins în primul rând ( l = 1).

Efectuăm transformarea Jordan cu elementul X13 = 2, obținem a doua soluție de referință X2 = (0,0,3,21,42,0) cu baza B2 = (A3, A4, A5). (Tabelul 26.2)

Această soluție nu este optimă, deoarece vectorul A2 are o estimare negativă Δ2 = - 6. Pentru a îmbunătăți soluția, este necesar să se introducă vectorul A2 în baza soluției de referință.

Determinăm numărul vectorului derivat din bază. Pentru a face acest lucru, calculăm parametrul θ 02 pentru a doua coloană, este egal cu 7 pentru l = 2. În consecință, derivăm al doilea vector de bază A4 din bază. Efectuăm transformarea Jordan cu elementul x 22 = 3, obținem a treia soluție de referință X3 = (0,7,10,0,63,0) B2 = (A3, A2, A5) (Tabelul 26.3).

Această soluție este singura optimă, deoarece pentru toți vectorii care nu sunt incluși în bază estimările sunt pozitive

Δ 1 = 7/2, Δ 4 = 2, Δ 6 = 7/2.

Răspuns: max Z(X) = 201 la X = (0,7,10,0,63).

Metoda de programare liniară în analiza economică

Metoda de programare liniară face posibila justificarea celei mai optime solutii economice in conditii de restrictii severe legate de resursele folosite in productie (mijloace fixe, materiale, resurse de munca). Utilizarea acestei metode în analiza economică face posibilă rezolvarea problemelor legate în principal de planificarea activităților unei organizații. Această metodă ajută la determinarea valori optime producția, precum și direcția de utilizare cât mai eficientă a resurselor de producție de care dispune organizația.

Prin această metodă se rezolvă așa-numitele probleme extreme, care constă în găsirea valorilor extreme, adică a maximului și minimului de funcții ale mărimilor variabile.

Această perioadă se bazează pe rezolvarea unui sistem de ecuații liniare în cazurile în care fenomenele economice analizate sunt legate printr-o dependență liniară, strict funcțională. Metoda de programare liniară este utilizată pentru a analiza variabilele în prezența anumitor factori limitatori.

Este foarte comun să se rezolve așa-numita problemă de transport folosind metoda de programare liniară. Conținutul acestei sarcini este de a minimiza costurile suportate în legătură cu operațiunea Vehicul sub restricțiile existente privind numărul de vehicule, capacitatea lor de transport, durata de funcționare a acestora, în cazul în care este nevoie de deservire a numărului maxim de clienți.

În plus, această metodă este utilizată pe scară largă în rezolvarea problemei de programare. Această sarcină constă într-o astfel de distribuție a timpului de funcționare pentru personalul unei organizații date, care ar fi cea mai acceptabilă atât pentru membrii acestui personal, cât și pentru clienții organizației.

Această sarcină este de a maximiza numărul de clienți deserviți în condiții de limitare a numărului de membri ai personalului disponibil, precum și a fondului de timp de lucru.

Astfel, metoda programării liniare este foarte comună în analiza plasării și utilizării diverselor tipuri de resurse, precum și în procesul de planificare și prognoză a activităților organizațiilor.

Cu toate acestea, programarea matematică poate fi aplicată și acelor fenomene economice, relația dintre care nu este liniară. În acest scop, pot fi utilizate metode de programare neliniară, dinamică și convexă.

Programarea neliniară se bazează pe natura neliniară a funcției obiectiv sau a constrângerilor, sau ambele. Formele funcției obiective și constrângerile de inegalitate în aceste condiții pot fi diferite.

Programarea neliniară este utilizată în analiza economică, în special, atunci când se stabilește relația dintre indicatorii care exprimă eficiența activităților unei organizații și volumul acestei activități, structura costurilor de producție, condițiile pieței etc.

Programarea dinamică se bazează pe construirea unui arbore de decizie. Fiecare nivel al acestui arbore servește drept etapă pentru determinarea consecințelor unei decizii anterioare și pentru eliminarea opțiunilor ineficiente pentru acea decizie. Astfel, programarea dinamică are o natură în mai multe etape, în mai multe etape. Acest tip de programare este folosit în analiza economică pentru a găsi optiuni optime dezvoltarea organizației atât în ​​prezent, cât și în viitor.

Programarea convexă este un tip de programare neliniară. Acest tip de programare exprimă natura neliniară a relației dintre rezultatele activităților unei organizații și costurile acesteia. Programarea convexă (aka concavă) analizează funcțiile obiective convexe și sistemele de constrângeri convexe (puncte de fezabilitate). Programare convexă aplicată în analiză activitate economicăîn vederea minimizării costurilor, şi concavă - în vederea maximizării veniturilor în condiţiile restricţiilor existente asupra acţiunii factorilor care influenţează în sens invers indicatorii analizaţi. În consecință, cu tipurile de programare luate în considerare, funcțiile obiectiv convexe sunt minimizate, iar funcțiile obiectiv concave sunt maximizate.

Programare liniară este o tehnică de modelare matematică concepută pentru a optimiza utilizarea resurselor limitate. LP este utilizat cu succes în domeniul militar, industrie, agricultură, industria transporturilor, economie, sistemul de sănătate și chiar în științe sociale. Utilizarea pe scară largă a acestei metode este susținută și de algoritmi de computer extrem de eficienți care implementează această metodă. Algoritmii de optimizare pentru alte tipuri mai complexe de modele și probleme de cercetare operațională (OR), inclusiv programarea cu numere întregi, neliniare și stocastică, se bazează pe algoritmi de programare liniară.

Problema de optimizare este o problemă economică și matematică care constă în găsirea valorii optime (maximum sau minim) a funcției obiectiv, iar valorile variabilelor trebuie să aparțină unui anumit interval de valori acceptabile.

În forma sa cea mai generală, problema de programare liniară este scrisă matematic după cum urmează:

Unde X = (x 1 , X 2 , ... , X n ) ; W– gama de valori admisibile ale variabilelor X 1 , X 2 , ... , X n ;f(X)- funcție obiectivă.

Pentru a rezolva o problemă de optimizare este suficient să găsim soluția optimă a acesteia, adică. indica faptul că la orice .

O problemă de optimizare este de nerezolvat dacă nu are o soluție optimă. În special, problema maximizării va fi de nerezolvat dacă funcția obiectiv f(X) nu este mărginită de sus pe mulţimea admisibilă W.

Metodele de rezolvare a problemelor de optimizare depind atât de tipul funcției obiectiv f(X), și din structura mulțimii admisibile W. Dacă funcția țintă din problemă este o funcție n variabile, atunci metodele de rezolvare se numesc metode de programare matematică.

Caracteristicile problemelor de programare liniară sunt următoarele:

indicele de optimitate f(X) este o funcție liniară a elementelor soluției X = (x 1 , X 2 , ... , X n ) ;

condiţiile restrictive impuse soluţiilor posibile iau forma egalităţilor sau inegalităţilor liniare.

Problemă de programare liniară se numește problemă de cercetare operațională, al cărei model matematic are forma:

(2) (3) (4) (5)

În acest caz, sistemul de ecuații liniare (3) și inegalități (4), (5), care determină setul admisibil de soluții ale problemei W, numit sistem de restricții probleme de programare liniară și o funcție liniară f(X) numit funcția țintă sau criteriul de optimitate .

Soluție valabilă este o colecție de numere ( plan ) X = (X 1 , X 2 , ... , X n ) , satisfacând constrângerile problemei. Soluție optimă – acesta este un plan în care funcția obiectiv își ia valoarea maximă (minimă).

Dacă modelul matematic al unei probleme de programare liniară are forma:

apoi spun că problema este prezentată în formă canonică .

Orice problemă de programare liniară poate fi redusă la o problemă de programare liniară în formă canonică. Pentru a face acest lucru, în cazul general, trebuie să puteți reduce problema de maximizare la problema de minimizare; trece de la constrângeri de inegalitate la constrângeri de egalitate și înlocuiește variabilele care nu se supun condiției de non-negativitate. Maximizarea unei anumite funcții echivalează cu minimizarea aceleiași funcții luate cu semnul opus și invers.

Regula pentru aducerea unei probleme de programare liniară la forma canonică este următoarea:

dacă în problema inițială este necesar să se determine maximul unei funcții liniare, atunci ar trebui să schimbați semnul și să căutați minimul acestei funcții;

dacă partea dreaptă a restricțiilor este negativă, atunci această restricție trebuie înmulțită cu -1;

dacă există inegalități între restricții, atunci prin introducerea unor variabile suplimentare nenegative acestea se transformă în egalități;

dacă vreo variabilă X j nu are restricții de semn, atunci este înlocuit (în funcția obiectiv și în toate restricțiile) cu diferența dintre două variabile noi nenegative: X 3 = x 3 + - X 3 - , Unde X 3 + , X 3 - ≥ 0 .

Exemplul 1. Reducerea problemei de programare liniară la formă canonică:

min L = 2x 1 +x 2 -X 3 ; 2x 2 -X 3 ≤ 5; X 1 +x 2 -X 3 ≥ -1; 2x 1 -X 2 ≤ -3; X 1 ≤ 0; X 2 ≥ 0; X 3 ≥ 0.

Să introducem variabile de nivelare în fiecare ecuație a sistemului de constrângeri X 4 , X 5 , X 6 . Sistemul va fi scris sub formă de egalități, iar în prima și a treia ecuație a sistemului de constrângeri variabilele X 4 , X 6 sunt introduse în partea stângă cu semnul „+”, iar în a doua ecuație variabila X 5 este introdus cu semnul „-”.

2x 2 -X 3 +x 4 = 5; X 1 +x 2 -X 3 -X 5 = -1; 2x 1 -X 2 +x 6 = -3; X 4 ≥ 0; X 5 ≥ 0; X 6 ≥ 0.

Termenii liberi în forma canonică trebuie să fie pozitivi; pentru a face acest lucru, înmulțiți ultimele două ecuații cu -1:

2x 2 -X 3 +x 4 = 5; -X 1 -X 2 +x 3 +x 5 = 1; -2x 1 +x 2 -X 6 = 3.

Metoda simplex pentru rezolvarea problemelor de programare liniară.

Algoritmul metodei simplex găsește soluția optimă luând în considerare un număr limitat de soluții de bază fezabile. Algoritmul metodei simplex începe întotdeauna cu o soluție de bază fezabilă și apoi încearcă să găsească o altă soluție de bază fezabilă care „îmbunătățește” valoarea funcției obiectiv. Acest lucru este posibil numai dacă o creștere a oricărei variabile zero (nebază) duce la o îmbunătățire a valorii funcției obiectiv. Dar pentru ca o variabilă nebază să devină pozitivă, una dintre variabilele de bază curente trebuie setată la zero, adică. converti în non-bază. Acest lucru este necesar pentru ca noua soluție să conțină exact m variabile de bază. În conformitate cu terminologia metodei simplex, este apelată variabila zero selectată intrare (la bază), iar variabila de bază care trebuie șters este exclus (de la bază).

Să numim două reguli pentru selectarea variabilelor de intrare și excludere în metoda simplex conditie de optimitate Și condiția de admisibilitate . Să formulăm aceste reguli și să luăm în considerare, de asemenea, succesiunea de acțiuni efectuate la implementarea metodei simplex.

Stare de optimitate. Variabila de intrare în problema de maximizare (minimizare) este o variabilă nebază care are cel mai mare coeficient negativ (pozitiv) în ţintă-linia. Dacă în ţintă-line conține mai mulți astfel de coeficienți, atunci alegerea variabilei introduse se face în mod arbitrar. Soluția optimă se atinge atunci când ţintă-line, toți coeficienții pentru variabilele nebazice vor fi nenegativi (nepozitivi).

Condiție de admisibilitate. În ambele probleme de maximizare și minimizare, variabila de bază pentru care raportul dintre valoarea părții drepte a constrângerii și coeficientul pozitiv al coloanei de conducere este minimă este selectată ca fiind cea exclusă. Dacă există mai multe variabile de bază cu această proprietate, atunci alegerea variabilei excluse este arbitrară.

Să prezentăm un algoritm pentru rezolvarea unei probleme de programare liniară de găsire a unui maxim folosind tabele simplex.

F = с 1 x 1 +с 2 x 2 +…+с n x n max

x 1 0, x 2 0,…, x n 0.

primul pas. Introducem variabile suplimentare și scriem sistemul rezultat de ecuații și funcția liniară sub forma unui sistem extins.

F–c 1 x 1 –c 2 x 2 –…–c n x n =0=c p.

al 2-lea pas. Compunem tabelul simplex inițial.

al 3-lea pas. Verificăm îndeplinirea criteriului de optimitate - prezența coeficienților negativi în ultima linie. Dacă nu există, atunci soluția este optimă și F * =c o, variabilele de bază sunt egale cu coeficienții corespunzători b j, variabilele nebazice sunt egale cu zero, adică X * =(b 1,b 2,..., b m, 0,…, 0).

al 4-lea pas. Dacă nu este îndeplinit criteriul de optimitate, atunci cel mai mare coeficient negativ absolut din ultimul rând (estimat) determină coloana de rezoluție s.

Pentru a determina linia de rezoluție, calculăm rapoartele de evaluare și completați ultima coloană a tabelului.

Raportul estimat al rândului i este

 dacă b i şi a este au semne diferite;

 dacă b i =0 și a este<0;

 dacă a este =0;

0 dacă b i =0 și a este >0;

În coloana relaţiilor evaluative găsim elementul minim min care definește șirul de activare g.

Dacă nu există un minim, atunci problema nu are un I optim final și este de nerezolvat.

La intersecția rândului și coloanei de rezoluție există un element de rezolvare a gs.

al 5-lea pas. Să construim următorul tabel. Pentru aceasta

Să trecem la al treilea pas.

Metoda M Uneori, la rezolvarea unui ZLP, matricea de coeficienți pentru constrângeri de sistem necunoscute nu are coloane unitare din care poate fi compusă o matrice unitară, adică. apare o problemă în alegerea variabilelor de bază sau soluția inițială este inacceptabilă. În astfel de cazuri utilizați metoda bazei artificiale (M - metoda).În toate restricțiile în care nu există variabile de bază, variabile artificiale. Variabilele artificiale sunt introduse în funcția obiectiv cu un coeficient (- M) pentru probleme cu max și cu un coeficient (+ M) pentru probleme cu min, unde M este un număr pozitiv suficient de mare. Apoi problema extinsă este rezolvată folosind regulile metodei simplex. Dacă toate variabilele artificiale sunt egale cu zero, i.e. sunt excluse din bază, atunci fie se va obține o soluție optimă a problemei inițiale, fie problema inițială este rezolvată în continuare și se găsește soluția optimă a acesteia sau se stabilește insolubilitatea acesteia. Dacă cel puțin una dintre variabilele artificiale se dovedește a fi diferită de zero, atunci problema inițială nu are soluție

Pentru a permite applet-ului să ruleze pe computer, trebuie să faceți următoarele - faceți clic pe Start>Panou de control>Programe>Java. În fereastra Panoului de control Java, selectați fila Securitate, faceți clic pe butonul Editare listă site-uri, butonul de adăugare și inserați calea către această pagină din bara de adrese a browserului în câmpul liber. Apoi, faceți clic pe OK, apoi reporniți computerul.

Pentru a lansa appletul, faceți clic pe butonul „Simplex”. Dacă butonul „Simplex” nu este vizibil deasupra acestei linii, atunci Java nu este instalat pe computer.

După ce faceți clic pe butonul „Simplex”, apare prima fereastră pentru introducerea numărului de variabile și a numărului de constrângeri ale problemei pe metoda simplex.

După ce faceți clic pe butonul „ok”, apare o fereastră pentru introducerea datelor rămase ale problemei folosind metoda simplex: modul de afișare (fracții zecimale sau ordinare), tipul sarcinii criteriu min sau max, introducerea coeficienților funcției obiectiv și coeficienții sistemului de constrângeri cu semnele „≤”, „ ≥ „sau „=", nu este necesar să se introducă restricții de forma x i ≥ 0, le ia în considerare în algoritmul său.

După ce faceți clic pe butonul „Rezolvare”, apare o fereastră cu rezultatele rezolvării problemei .Fereastra este formată din două părți; în partea de sus există un câmp de text care conține o descriere a reducerii problemei inițiale la forma canonică, care este utilizată pentru a compila primul tabel simplex. În partea de jos a ferestrei, într-un panou cu file, există tabele simplex ale fiecărei iterații cu un mic câmp de text în partea de jos care indică coloana de rezoluție, rândul de rezoluție și alte informații, ceea ce face antrenamentul programului. În fila cu tabelul optim (ultimul), soluția optimă rezultată a problemei este afișată în câmpul de text.

Trimiteți orice erori pe care le observați și comentarii despre applet la: [email protected] sau sunați la 8 962 700 77 06, pentru care vă vom fi foarte recunoscători.

Program cu metoda M

Program pentru rezolvarea unei probleme de transport

Iată o rezolvare manuală (nu applet) a două probleme folosind metoda simplex (asemănătoare soluției applet) cu explicații detaliate pentru a înțelege algoritmul de rezolvare a problemelor. Prima problemă conține doar semne de inegalitate „≤” (problema cu bază inițială), a doua poate conține semne „≥”, „≤” sau „=” (problema cu bază artificială), acestea sunt rezolvate diferit.

Metoda simplex, rezolvarea unei probleme cu o bază inițială

1)Metoda simplex pentru o problemă cu o bază inițială (toate semnele de constrângeri de inegalitate „ ≤ „).

Să scriem problema în canonic formă, adică rescriem restricțiile inegalității sub formă de egalități, adăugând bilanț variabile:

Acest sistem este un sistem cu o bază (baza s 1, s 2, s 3, fiecare dintre ele este inclusă într-o singură ecuație a sistemului cu un coeficient de 1), x 1 și x 2 sunt variabile libere. Problemele care trebuie rezolvate prin metoda simplex trebuie să aibă următoarele două proprietăți:
-sistemul de constrângeri trebuie să fie un sistem de ecuaţii cu bază;
-termenii liberi ai tuturor ecuatiilor din sistem trebuie sa fie nenegativi.

Sistemul rezultat este un sistem cu o bază și termenii săi liberi sunt nenegativi, deci se poate aplica metoda simplex. Să creăm primul tabel simplex (Iterația 0), adică. un tabel de coeficienți ai funcției obiectiv și un sistem de ecuații pentru variabilele corespunzătoare. Aici „BP” înseamnă coloana variabilelor de bază, „Soluție” înseamnă coloana părților din dreapta ale ecuațiilor sistemului. Soluția nu este optimă, pentru că există coeficienți negativi în rândul z.

iterația 0

Pentru a îmbunătăți soluția, trecem la următoarea iterație și obținem următorul tabel simplex. Pentru a face acest lucru, trebuie să selectați activați coloana, adică o variabilă care va fi inclusă în bază la următoarea iterație. Este selectat de cel mai mare coeficient negativ absolut din rândul z (în problema maximă) - în iterația inițială aceasta este coloana x 2 (coeficientul -6).

Apoi selectați activați șirul, adică o variabilă care va părăsi baza la următoarea iterație. Este selectat după cel mai mic raport al coloanei „Decizie” față de elementele pozitive corespunzătoare ale coloanei de rezoluție (coloana „Ratio”) - în iterația inițială acesta este rândul s 3 (coeficientul 20).

Element permisiv se află la intersecția coloanei de rezolvare și a rândului de rezolvare, celula sa este evidențiată în culoare, este egală cu 1. Prin urmare, la următoarea iterație, variabila x 2 va înlocui s 3 în bază. Rețineți că relația nu este căutată în șirul z; acolo este plasată o liniuță „-”. Dacă există relații minime identice, atunci oricare dintre ele este selectată. Dacă toți coeficienții din coloana rezoluției sunt mai mici sau egali cu 0, atunci soluția problemei este infinită.

Să completăm următorul tabel „Iterația 1”. O vom obține din tabelul „Iterație 0”. Scopul transformărilor ulterioare este de a transforma coloana de rezoluție x2 într-o coloană de unitate (cu un unu în loc de elementul de rezoluție și cu zerouri în loc de elementele rămase).

1) Calculați rândul x 2 din tabelul „Iterația 1”. În primul rând, împărțim toți membrii rândului de rezolvare s 3 din tabelul „Iterația 0” la elementul de rezolvare (în acest caz este egal cu 1) din acest tabel, obținem rândul x 2 în tabelul „Iterația 1” . Deoarece elementul de rezolvare în acest caz este egal cu 1, apoi rândul s 3 din tabelul „Iterația 0” va coincide cu rândul x 2 din tabelul „Iterația 1”. Rândul x 2 din tabelul Iterația 1 am obținut 0 1 0 0 1 20, rândurile rămase din tabelul Iterația 1 vor fi obținute din acest rând și rândurile din tabelul Iterația 0 după cum urmează:

2) Calculul rândului z al tabelului „Iterația 1”. În locul lui -6 în primul rând (z-rând) în coloana x2 a tabelului Iterația 0, ar trebui să existe un 0 în primul rând al tabelului Iterația 1. Pentru a face acest lucru, înmulțiți toate elementele rândului x 2 din tabelul „Iterația 1” 0 1 0 0 1 20 cu 6, obținem 0 6 0 0 6 120 și adăugăm acest rând cu primul rând (z - rând) din tabelul „Iterația 0” -4 -6 0 0 0 0, obținem -4 0 0 0 6 120. În coloana x 2 apare un zero 0, scopul este atins. Elementele coloanei de rezoluție x 2 sunt evidențiate cu roșu.

3) Calculul rândului s 1 din tabelul „Iterația 1”. În loc de 1 în s 1 rând al tabelului „Iterația 0” ar trebui să existe un 0 în tabelul „Iterația 1”. Pentru a face acest lucru, înmulțiți toate elementele rândului x 2 din tabelul „Iterația 1” 0 1 0 0 1 20 cu -1, obțineți 0 -1 0 0 -1 -20 și adăugați acest rând cu s 1 - rândul tabelul „Iterația 0” 2 1 1 0 0 64, obținem rândul 2 0 1 0 -1 44. În coloana x 2 obținem 0 necesar.

4) Calculați rândul s 2 din tabelul „Iterația 1”. În locul 3 în rândul s 2 al tabelului „Iterația 0” ar trebui să fie 0 în tabelul „Iterația 1”. Pentru a face acest lucru, înmulțiți toate elementele rândului x 2 din tabelul „Iterația 1” 0 1 0 0 1 20 cu -3, obțineți 0 -3 0 0 -3 -60 și adăugați acest rând cu s 2 - rândul tabelului „Iterația 0” 1 3 0 1 0 72, obținem rândul 1 0 0 1 -3 12. În coloana x 2 se obține 0. Coloana x 2 din tabelul „Iterația 1” a devenit o unitate , conține unul 1 și restul 0.

Rândurile tabelului „Iterația 1” sunt obținute prin următoarea regulă:

Rând nou = Rând vechi – (Coeficient de coloană de rezoluție a rândului vechi)* (Rând de rezoluție nou).

De exemplu, pentru un șir z avem:

Vechiul z-string (-4 -6 0 0 0 0)
-(-6)*Linie de rezoluție nouă -(0-6 0 0 -6 -120)
= șir Z nou(-4 0 0 0 6 120) .

Pentru următoarele tabele, recalcularea elementelor de tabel se face într-un mod similar, așa că o omitem.

iterația 1

Rezolvarea coloanei x 1, rezolvarea rândului s 2, s 2 părăsește baza, x 1 intră în bază. Exact în același mod, obținem tabelele simplex rămase până când obținem un tabel cu toți coeficienții pozitivi în rândul z. Acesta este un semn al unei mese optime.

Iterația 2

Rezolvând coloana s 3, rezolvând rândul s 1, s 1 părăsește baza, s 3 intră în bază.

Iterația 3

În rândul z, toți coeficienții sunt nenegativi, prin urmare, se obține soluția optimă x 1 = 24, x 2 = 16, z max = 192.

Metoda simplex, rezolvarea unei probleme pe bază artificială

2) Să rezolvăm problema pe o bază artificială (cel puțin un semn de constrângere de inegalitate „≥” sau „=”).

Să scriem problema în formă canonică (sub forma unui sistem de ecuații, care necesită metoda simplex), pentru a face acest lucru introducem două variabile x 3 ≥ 0 și x 4 ≥ 0, obținem:

Sistemul de restricții oferă o singură variabilă de bază admisibilă x 4, doar că este inclusă într-o singură ecuație în a treia cu coeficient de 1, deci adăugăm variabilele artificiale R 1 ≥ 0 și R 2 ≥ 0 la prima și a doua ecuație. pentru ca metoda simplex să poată fi aplicată, ecuațiile de constrângere a sistemului trebuie să fie un sistem cu o bază, i.e. în fiecare ecuație trebuie să existe o variabilă cu coeficient de 1, care este inclusă într-o singură ecuație a sistemului, în cazul nostru acestea sunt R 1, R 2 și x 4. Am primit așa-numita sarcină M:

Acest sistem este un sistem cu o bază, în care R 1, R 2 și x 4 sunt variabile de bază, iar x 1, x 2 și x 3 sunt variabile libere, termenii liberi ai tuturor ecuațiilor sunt nenegativi. Prin urmare, metoda simplex poate fi folosită pentru a rezolva problema. Să notăm tabelul simplex inițial:

iterația 0

Linia „Evaluare” a fost adăugată la tabel pentru probleme cu o bază artificială. Se obține prin însumarea coeficienților corespunzători ai rândurilor cu variabile artificiale (R) cu semnul opus. Acesta va fi prezent în tabel atâta timp cât cel puțin una dintre variabilele artificiale este în bază. Pe baza celui mai mare coeficient modulo negativ al liniei „Evaluare”, coloana de rezolvare este determinată în timp ce se află în tabel. Când rândul „Evaluare” părăsește tabelul (nu există variabile artificiale în bază), coloana de rezolvare va fi determinată de rândul z, ca în problema cu baza inițială. În acest tabel, coloana de rezolvare este x 2, este selectată pe baza celui mai mare scor negativ absolut (-7). Rândul de rezolvare R 2 este selectat pe baza celui mai mic raport dintre coloanele „Soluție” și elementele pozitive corespunzătoare ale coloanei de rezolvare, ca în problema fără variabile artificiale. Aceasta înseamnă că la următoarea iterație variabila x2 va trece de la liber la bază, iar variabila R2 va trece de la bază la liberă. Să scriem următorul tabel simplex:

Rezolvând coloana x 1, rezolvând rândul R 1, R 1 părăsește baza, x 1 intră în bază. După aceasta, nu mai există variabile artificiale în bază, deci nu există nicio linie „Evaluare” în următorul tabel:

iterația 2

Apoi, coloana de rezoluție este selectată de rândul z. În rândul z, toți coeficienții sunt nenegativi, cu excepția coeficientului pentru variabila artificială R 1, care nu afectează optimitatea atunci când variabilele artificiale părăsesc baza. În consecință, se obține soluția optimă x 1 = 6/5; x 2 = 3/5; z max = 72/5.

Cazuri speciale de utilizare a metodei simplex

1) Când linia dreaptă (dacă se consideră o problemă de programare liniară bidimensională, iar în cazul general un hiperplan) care reprezintă funcția obiectiv este paralelă cu dreapta (hiperplanul) corespunzătoare uneia dintre constrângerile de inegalitate (care la punctul optim este satisfăcut ca o egalitate exactă), funcția obiectiv ia unul și este, de asemenea, o valoare optimă la un anumit set de puncte de la limita regiunii soluțiilor fezabile. Aceste soluții se numesc alternativă solutii optime . Prezența soluțiilor alternative poate fi determinată folosind tabelul simplex optim. Dacă rândul z al tabelului optim conține zero coeficienți ai variabilelor nebaze, atunci există soluții alternative.

2) Dacă în coloana de rezoluție a tabelului simplex toți coeficienții sunt mai mici sau egali cu zero, atunci este imposibil să selectați un rând de rezolvare, în acest caz soluția este nelimitată.

3) Dacă constrângerile unei probleme de programare liniară sunt inconsistente (adică nu pot fi satisfăcute simultan), atunci problema nu are soluții fezabile. Această situație nu poate apărea dacă toate inegalitățile care alcătuiesc sistemul de restricții sunt de tipul „≤” cu laturile drepte nenegative, deoarece în acest caz, variabilele suplimentare pot constitui o soluție fezabilă. Pentru alte tipuri de constrângeri se folosesc variabile artificiale. Dacă problema are o soluție, atunci în tabelul optim nu există variabile artificiale (R i) în bază. Dacă sunt acolo, atunci problema nu are soluții.

Dacă trebuie să rezolvați o problemă de programare liniară folosind tabele simplex, atunci nostru serviciu online vă va fi de mare ajutor. Metoda simplex implică căutarea secvențială prin toate vârfurile intervalului de valori acceptabile 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 este îmbunătățită la fiecare pas ulterior. Această soluție se numește de bază. Iată secvența de acțiuni atunci când se rezolvă 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 pe care să se includă pentru a recalcula tabelul simplex. Pentru a face acest lucru, căutați prin coloana cu termeni liberi și găsiți un element negativ în ea. Linia cu un element negativ se va numi lider. În el găsim elementul negativ maxim în modul, coloana corespunzătoare este cea slave. Dacă există valori negative printre termenii liberi, dar nu există niciunul în rândul corespunzător, atunci un astfel de tabel nu va avea soluții. Variabila din rândul de început situat în coloana de termeni liberi este exclusă din bază, iar variabila corespunzătoare coloanei de început este inclusă în bază.

Tabelul 1.

Al treilea pas. În al treilea pas, recalculăm întregul tabel simplex folosind formule speciale; aceste formule pot fi văzute folosind.

Al patrulea pas. Dacă după recalculare au rămas elemente negative în coloana termenilor 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 șirul F sunt pozitive. Dacă nu este cazul, atunci este necesar să îmbunătățim soluția, pentru care găsim rândul și coloana de început pentru următoarea recalculare folosind următorul algoritm. Inițial, găsim numărul minim negativ în șirul 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 termenul liber corespunzător și elementul din coloana de început, cu condiția ca acestea să fie pozitive. Raportul minim vă va permite să determinați linia de conducere. Recalculăm din nou tabelul folosind formulele, adică. treceți la pasul 3.

>> >> >> Metoda simplex

Metoda simplex

Orice soluție poate fi găsită metoda simplex. Înainte de a utiliza metoda simplex, ar trebui să scrieți problema originală sub forma unei probleme de programare liniară de bază, dacă nu are o astfel de formă.

Metoda simplex pentru rezolvarea unei probleme de programare liniară se bazează pe trecerea de la un plan de referință la altul, în care valoarea funcției obiectiv crește(cu condiția ca această problemă să aibă un plan optim și fiecare dintre planurile sale de suport să fie nedegenerat). Tranziția specificată este posibilă dacă se cunoaște un plan de referință inițial. Să luăm în considerare o problemă pentru care acest plan poate fi scris direct.

Să fie necesar să se găsească valoarea maximă a funcției

in conditii

Aici și – date constante

Forma vectorială a acestei probleme este următoarea: găsiți maximul funcției

in conditii

atunci, prin definiție, planul de referință este planul de referință al acestei probleme (ultimele componente ale vectorului X sunt egale cu zero). Acest plan este determinat de sistemul de vectori unitari care stau la baza m- măsurat spaţiu. Prin urmare, fiecare dintre vectori și poate fi reprezentat și ca o combinație liniară de vectori de o bază dată. Lăsa

Sa punem Din moment ce vectori – singur, apoi și

Teorema 5

(un semn al optimității planului de referință). Plan de sarcini de bază (22) – (24) este optim dacă pentru orice j

Teorema 6.

Dacă pentru unele j=k și nu există numere pozitive printre numere , apoi funcţia obiectiv(22) sarcini (22) – (24) nu se limitează la numeroasele sale planuri.

Teorema 7.

Dacă planul de referință X al sarcinii (22) – (24)nedegeneratȘi , Dar printre numeresunt pozitive (nu toate), atunci există un plan de referință X" astfel încât

Teoremele formulate permit să se verifice dacă planul de referință găsit este optim și să se identifice fezabilitatea trecerii la un nou plan de referință.

Este mai convenabil să se studieze planul de referință pentru optimitate, precum și procesul de calcul ulterior, dacă condițiile problemei și datele inițiale obținute după determinarea planului de referință inițial sunt scrise așa cum se arată în tabel. 3.

În coloana C 6 a acestui tabel se scriu coeficienții pentru funcțiile obiectiv necunoscute, având aceiași indici ca și vectorii bazei date.

Componentele pozitive ale planului de referință original sunt scrise în coloană, iar în urma calculelor se obțin în ea componentele pozitive ale planului optim. Coloanele de vectori reprezintă coeficienții expansiunii acestor vectori în vectorii unei baze date.

În tabel 3 primul m rândurile sunt determinate de datele inițiale ale problemei, iar indicatorii rândului (m+1) sunt calculați. În această linie, în coloana de vectori, scrieți valoarea funcției obiectiv pe care o ia pentru un plan de referință dat, iar în coloana de vectori – sens

Valoarea lui Z j se găsește ca produs scalar dintre un vector și un vector

Valoarea este egală cu produsul scalar al vectorului P 0 și al vectorului:

După completarea tabelului 3, planul de referință original este verificat pentru optimitatea. Pentru a face acest lucru, priviți prin elementele celui de-al treilea rând al tabelului. Ca urmare, poate apărea unul dintre următoarele trei cazuri:

1) pentru j=m+1, (la ). Prin urmare, în acest caz, numere pentru toată lumea j de la 1 la n;

2) pentru unii j, și toate valorile corespunzătoare acestui indice

3) pentru unii indici j, și pentru fiecare astfel j cel puțin unul dintre numere este pozitiv.

În primul caz, pe baza criteriului de optimitate, planul de referință inițial este optim. În al doilea caz, funcția obiectiv nu este limitată de sus pe setul de planuri, iar în al treilea caz, puteți trece de la planul inițial la un nou plan de referință, în care valoarea funcției obiectiv va crește. Această tranziție de la un plan de referință la altul se realizează prin excluderea oricăruia dintre vectori din baza originală și introducerea unui nou vector în acesta. Ca vector introdus în bază, puteți lua oricare dintre vectorii cu indicele j, pentru care . Să presupunem, de exemplu, că se decide introducerea unui vector în bază

Pentru a determina vectorul care trebuie exclus din bază, găsiți pentru toate Fie ca acest minim să fie atins când i=r. Apoi vectorul este exclus din bază și numărul este numit element permisiv.

Se numesc coloana și rândul la intersecția cărora există un element de rezolvare ghiduri.

După selectarea rândului de ghidare și a coloanei de ghidare, se găsesc un nou plan de referință și coeficienți de expansiune vectorială prin vectorii noii baze corespunzători noului plan de referință. Acest lucru este ușor de implementat dacă utilizați metoda Jordan–Gauss. În acest caz, se poate demonstra că componentele pozitive ale noului plan de referință sunt calculate folosind formulele

(25)

iar coeficienții de expansiune a vectorilor prin vectorii noii baze corespunzători noului plan de referință - conform formulelor

(26)

După calcul și conform formulelor (25) și (26), valorile acestora sunt introduse în tabel. 4. Elementele din rândul al treilea al acestui tabel pot fi calculate fie folosind formule

(27)

(28)

sau pe baza definirii lor.

Tabelul 3

Tabelul 4

Prezența a două moduri de a găsi elementele rândului al treilea vă permite să controlați corectitudinea calculelor efectuate.

Din formula (27) rezultă că la trecerea de la un plan de referință la altul, cel mai indicat este să se introducă în bază un vector având indicele j, la care maximul în valoare absolută este numărul . Totuși, pentru a simplifica procesul de calcul, în viitor vom determina vectorul introdus în bază pe baza valorii maxime absolute a numerelor negative. Dacă există mai multe astfel de numere, atunci vom introduce în bază un vector care are același indice cu maximul numerelor definite de aceste numere.

Deci, trecerea de la un plan de referință la altul se reduce la trecerea de la un tabel simplex la altul. Elementele noului tabel simplex pot fi calculate atât folosind formulele recurente (25)-(28) cât și folosind regulile care decurg direct din acestea. Aceste reguli sunt după cum urmează.

În coloanele de vectori incluse în bază, la intersecția rândurilor și coloanelor de vectori cu același nume, sunt plasate unități, iar toate celelalte elemente ale acestor coloane sunt setate egale cu zero.

Elementele vectorilor și din rândul noului tabel simplex, în care se scrie vectorul introdus în bază, se obțin din elementele aceluiași rând al tabelului inițial prin împărțirea lor la valoarea elementului de rezoluție. În coloana din rândul vectorului de intrare, introduceți valoarea , unde k – indicele vectorului de intrare.

Elementele rămase ale coloanelor vectoriale și noul tabel simplex sunt calculate folosind regula triunghiului. Pentru a calcula oricare dintre aceste elemente, se găsesc trei numere:

1) un număr care se află în tabelul simplex original în locul elementului dorit al noului tabel simplex;

2) un număr din tabelul simplex original la intersecția rândului care conține elementul dorit din noul tabel simplex și coloana corespunzătoare vectorului introdus în bază;

3) un număr în noul tabel simplex la intersecția coloanei în care se află elementul necesar și rândul vectorului nou introdus în bază (după cum s-a menționat mai sus, acest rând este obținut din rândul tabelului simplex original prin împărțirea elementelor sale la elementul de rezoluție).

Aceste trei numere formează un fel de triunghi, două dintre ale cărui vârfuri corespund numerelor din tabelul simplex original, iar al treilea numărului din noul tabel simplex. Pentru a determina elementul necesar al noului tabel simplex, produsul dintre al doilea și al treilea este scăzut din primul număr.

După completarea noului tabel simplex, sunt examinate elementele rândului al treilea. Dacă totul este , atunci noul plan de referință este optim. Dacă printre numerele indicate există și negative, atunci, folosind succesiunea de acțiuni descrisă mai sus, se găsește un nou plan de referință. Acest proces este continuat până când fie se obține proiectarea optimă a problemei, fie se stabilește insolubilitatea acesteia.

Atunci când găsim o soluție la problema de programare liniară, am presupus că această problemă are planuri de suport și fiecare astfel de plan este nedegenerat. Dacă problema are planuri de suport degenerate, atunci la una dintre iterații una sau mai multe variabile ale planului de suport se pot dovedi a fi egale cu zero. Astfel, la trecerea de la un plan de referință la altul, valoarea funcției poate rămâne aceeași. Mai mult, este posibil ca funcția să-și păstreze valoarea pe parcursul mai multor iterații și, de asemenea, este posibil să se întoarcă la baza originală. În acest din urmă caz ​​ei spun de obicei ce s-a întâmplat buclă. Cu toate acestea, atunci când rezolvăm probleme practice, acest caz apare foarte rar, așa că nu ne vom opri asupra lui.

Deci, găsirea planului optim folosind metoda simplex include următorii pași:

1. Găsiți un plan de referință.

2. Alcătuiți un tabel simplex.

3. Aflați dacă există cel puțin un număr negativ. Dacă nu, atunci planul de referință găsit este optim. Dacă există numere negative printre numere, atunci acestea fie stabilesc imposibilitatea de rezolvare a problemei, fie trec la un nou plan de referință.

4. Găsiți ghidajele de coloane și rânduri. Coloana de ghidare este determinată de cel mai mare număr negativ în valoare absolută, iar rândul de ghidare este determinat de minimul raporturilor dintre componentele coloanei vectoriale și componentele pozitive ale coloanei de ghidare.

5. Cu ajutorul formulelor (25) – (28) se determină componentele pozitive ale noului plan de referință și coeficienții de expansiune vectorială Pijamale prin vectori ai noii baze și număr , . Toate aceste numere sunt scrise într-un nou tabel simplex.

6. Verificați optimitatea planului de referință găsit. Dacă planul nu este optim și este necesară trecerea la un nou plan de referință, atunci se revin la etapa 4, iar dacă se obține un plan optim sau se stabilește insolubilitatea, procesul de rezolvare a problemei este finalizat.

Exemplul 9.

Pentru fabricarea diverselor produse A,ÎNși C întreprinderea folosește trei tipuri variate materii prime. Ratele consumului de materii prime pentru producerea unui produs de fiecare tip, pretul unui produs A,ÎNȘi CU, precum și cantitatea totală de materii prime de fiecare tip care poate fi utilizată de întreprindere, sunt date în tabel. 5.

Tabelul 5

Produse A,ÎNȘi CU poate fi produs în orice proporție (vânzările sunt garantate), dar producția este limitată la materiile prime de fiecare tip alocate întreprinderii.

Întocmește un plan de producție pentru produse în care costul total al tuturor produselor produse de întreprindere este maxim.

Soluţie. Să creăm un model matematic al problemei. Lansare de produs necesară A notăm cu x 1, produse IN - prin , produse CU - prin . Întrucât există restricții asupra fondului de materii prime de fiecare tip alocat întreprinderii, variabilele trebuie să satisfacă următorul sistem de inegalități:

(29)

Costul total al produselor produse de întreprindere, sub rezerva eliberării x 1 produse A, produse ÎN si produse CU se ridică la

În funcție de conținutul lor economic, variabilele pot lua numai valori nenegative:

Astfel, ajungem la următoarea problemă matematică: dintre toate soluțiile nenegative ale sistemului de inegalități (29), se cere să găsim una la care funcția (30) ia valoarea maximă.

Să scriem această problemă sub forma unei probleme de programare liniară de bază. Pentru a face acest lucru, să trecem de la constrângerile de inegalitate la constrângerile de egalitate. Să introducem trei variabile suplimentare, în urma cărora restricțiile vor fi scrise sub forma unui sistem de ecuații

În termeni economici, aceste variabile suplimentare înseamnă cantitatea de materie primă de un tip sau altul care nu este utilizată într-un plan de producție dat. De exemplu, – Aceasta este cantitatea nefolosită de materii prime de tip I.

Scriem sistemul transformat de ecuații sub formă vectorială:

Din moment ce printre vectori Deoarece există trei vectori unitari, planul de referință poate fi scris direct pentru această problemă. Acesta este planul X=(0; 0; 0; 360; 192; 180), definit de un sistem de vectori unitari tridimensionali care formează baza unui spațiu vectorial tridimensional.

Compunem un tabel simplex pentru iterația I (Tabelul 6), calculăm valorile și verificăm optimitatea planului de referință inițial:

Pentru vectorii de bază

Tabelul 6

După cum se poate observa din Tabelul 6, valorile tuturor variabilelor principale sunt egale cu zero, iar variabilele suplimentare își iau valorile în conformitate cu constrângerile problemei. Aceste valori variabile corespund unui „plan” în care nu se produce nimic, nu se utilizează materii prime, iar valoarea funcției obiectiv este zero (adică nu există cost de producție). Acest plan, desigur, nu este optim.

Acest lucru poate fi văzut din a 4-a linie a tabelului. 6, deoarece conține trei numere negative: și Numerele negative nu indică doar posibilitatea creșterii costului total de producție, dar arată și cât de mult va crește această sumă atunci când o unitate dintr-unul sau altul tip de produs este introdusă în plan.

Deci, numărul - 9 înseamnă că atunci când un produs este inclus în planul de producție A asigură o creștere a producției cu 9 ruble. Dacă includeți un produs în planul de producție ÎNși C, atunci costul total al produselor fabricate va crește cu 10, respectiv 16 ruble. Prin urmare, din punct de vedere economic, este cel mai indicat să se includă produse în planul de producție CU. Același lucru trebuie făcut pe baza semnului formal al metodei simplex, deoarece numărul maxim negativ în valoare absolută se află în al 4-lea rând al coloanei vectoriale. R 3. Prin urmare, introducem vectorul în bază R 3. determinăm vectorul care trebuie exclus din bază. Pentru a face asta găsim

După ce am găsit numărul, am determinat astfel din punct de vedere economic câte produse CUîntreprinderea poate produce ţinând cont de ratele de consum şi volumele disponibile de materii prime de fiecare tip. Întrucât există 360, 192 și respectiv 180 kg de materii prime de acest tip, și pentru un produs CU necesare pentru a cheltui materiile prime de fiecare tip sunt 12, 8 și respectiv 3 kg, apoi numărul maxim de produse CU, care poate fi produs de întreprindere, este egal cu adică un factor limitator pentru producția de produse CU este volumul disponibil de materii prime de tip II. Ținând cont de disponibilitatea acesteia, compania poate produce 24 de produse CU.În acest caz, materiile prime de tip II vor fi utilizate integral.

Prin urmare, vectorul R 5 face obiectul excluderii din temei. Coloană vectorială R Rândurile de la 3 la al 2-lea sunt ghidajele. Compilăm un tabel pentru iterația II (Tabelul 7).

Tabelul 7

În primul rând, umplem linia vectorului nou introdus în bază, adică linia al cărei număr coincide cu numărul liniei de ghidare. Aici ghidul este a doua linie. Elementele acestui rând sunt în tabel. 7 se obțin din elementele corespunzătoare din tabelul 6 prin împărțirea lor la elementul de rezoluție (adică la 8). Mai mult, în coloană C b Notăm coeficientul în coloana vectorului introdus în bază. Apoi completăm elementele coloanelor pentru vectorii incluși în noua bază. În aceste coloane, la intersecția rândurilor și coloanelor de vectori cu același nume, punem unități, iar toate celelalte elemente sunt setate egale cu zero.

Pentru a determina elementele rămase ale tabelului. 7 aplicăm regula triunghiului. Aceste elemente pot fi calculate direct folosind formule de recurență.

Să calculăm elementele tabelului. 7 stând într-o coloană vectorială R 0 . Prima se află în primul rând al acestei coloane. Pentru a o calcula, găsim trei numere:

1) numărul din tabel. 6 la intersecția coloanei vectoriale R 0 și 1 linii (360);

2) numărul din tabel. 6 la intersecția coloanei vectoriale P 3 și 1 rânduri (12);

3) numărul din tabel. 7 la intersecția coloanei vectoriale R 0 și a doua rânduri (24).

Scăzând produsul celorlalte două din primul număr, găsim elementul cerut: 360 – 12 x 24 = 72; scrieți-l în primul rând al coloanei vectoriale R 0 filă. 7.

A doua coloană a vectorului R 0 filă. 7 a fost deja calculat mai devreme. Pentru a calcula cel de-al treilea element de coloană al unui vector R 0 găsim și trei numere. Primul dintre ele (180) este situat la intersecția celui de-al treilea rând și coloana vectorului R 0 filă. 6, al doilea (3) – la intersecția rândului 3 și coloanei vectorului P 3 mese 6, a treia (24) – la intersecția rândului 2 și coloanei vectorului R 0 filă. 8. Deci, elementul indicat este 180 - 24 x 3 = 108. Scriem numărul 108 în a treia linie a coloanei vectoriale R 0 filă. 7.

Sens F 0 în al 4-lea rând al coloanei aceluiași vector poate fi găsit în două moduri:

1) conform formulei, i.e.

2) după regula triunghiului; în acest caz, triunghiul este format din numerele 0, -16, 24. Această metodă conduce la același rezultat: 0 - (-16) x 24 = 384.

La determinarea elementelor de coloană vectorială folosind regula triunghiului R 0 al treilea număr, aflat la vârful inferior al triunghiului, a rămas neschimbat tot timpul și doar primele două numere s-au schimbat. Să luăm în considerare acest lucru atunci când găsim elementele coloanei vectoriale P 1 masă 7. Pentru a calcula elementele indicate, luăm primele două numere din coloanele de vectori P 1 și R 3 mese 6, iar al treilea număr este din tabel. 7. Acest număr se află la intersecția celui de-al doilea rând și coloana vectorului P 1 din ultimul tabel. Ca urmare, obținem valorile elementelor necesare: 18 – 12 x (3/4) =9; 5 – 3 x (3/4) = 11/4.

Număr în al 4-lea rând al coloanei vector P 1 masă 7 poate fi găsit în două moduri:

1) conform formulei Z 1 -C 1 = (C,P 1) -C 1 avem

2) conform regulii triunghiului obținem

În mod similar, găsim elementele coloanei vectoriale P 2 .

Elemente de coloană vectorială R 5 se calculează folosind regula triunghiului. Cu toate acestea, triunghiurile construite pentru a defini aceste elemente arată diferit.

La calcularea elementului din primul rând al coloanei specificate, se obține un triunghi format din numerele 0,12 și 1/8. Prin urmare, elementul necesar este 0 – 12x (1/8) = -3/2. Elementul din al 3-lea rând al acestei coloane este egal cu 0 - 3 x (1/8) = -3/8.

La finalizarea calculului tuturor elementelor tabelului. 7 în el se obțin un nou plan de referință și coeficienți de expansiune vectorială prin vectorii de bază P 4, P 3, P 6 și valorile și . După cum se poate vedea din acest tabel, noul plan de referință pentru sarcină este planul X=(0; 0; 24; 72; 0; 108). Cu acest plan de producție sunt produse 24 de produse CU iar 72 kg de materii prime de tip 1 și 108 kg de materii prime de tip III rămân neutilizate. Costul tuturor produselor produse în cadrul acestui plan este de 384 de ruble. Numerele indicate sunt scrise în coloana vectorială R 0 filă. 7. După cum puteți vedea, datele din această coloană reprezintă încă parametrii problemei luate în considerare, deși au suferit modificări semnificative. S-au schimbat și datele din alte coloane, iar conținutul lor economic a devenit mai complex. Deci, de exemplu, luați datele coloanei vectoriale R 2 . Numărul 1/2 din a doua linie a acestei coloane arată cât de mult ar trebui redusă producția de produse CU, dacă intenționați să lansați un produs ÎN. Numerele 9 și 3/2 în rândurile 1 și 3 ale vectorului P 2 arată, respectiv, câtă materie primă de tip I și II va fi necesară atunci când este inclusă în planul de producție pentru un produs ÎN, iar numărul - 2 din a patra linie arată că dacă este planificată lansarea unui produs ÎN, atunci acest lucru va asigura o creștere a producției în termeni de valoare cu 2 ruble. Cu alte cuvinte, dacă includeți un produs în planul de producție ÎN, atunci aceasta va necesita o reducere a producției de produs CU cu 1/2 unitate și va necesita costuri suplimentare de 9 kg de materii prime de tip I și 3/2 kg de materii prime de tip III, iar costul total al produselor fabricate în conformitate cu noul plan optim va crește cu 2 ruble. Astfel, numerele 9 și 3/2 acționează ca noi „norme” pentru costul materiilor prime de tipul I și III pentru fabricarea unui produs ÎN(după cum se poate observa din tabelul 6, anterior erau egale cu 15 și 3), ceea ce se explică printr-o scădere a producției de produse CU.

Datele coloanei vectoriale au, de asemenea, aceeași semnificație economică R 1 masă 7. Numerele scrise în coloana vectorului au un conținut economic ușor diferit R 5 . Numărul 1/8 din rândul 2 al acestei coloane arată că o creștere a volumului de materii prime de tip II cu 1 kg ar permite creșterea producției de produse CU cu 1/8 unități Totodată, ar fi necesare încă 3/2 kg de materii prime de tip I și 3/8 kg de materii prime de tip III. Creșterea producției de produse CU cu 1/8 unități va duce la o creștere a producției cu 2 ruble.

Din conținutul economic de mai sus al datelor din tabel. 7 rezultă că planul problemei găsit la iterația II nu este optim. Acest lucru poate fi văzut din a 4-a linie a tabelului. 7, deoarece în coloana vector P 2 din această linie este un număr negativ - 2. Aceasta înseamnă că vectorul trebuie introdus în bază P 2, adică noul plan ar trebui să prevadă producția de produse ÎN. La determinarea numărului posibil de produse de fabricat ÎN trebuie avută în vedere cantitatea disponibilă de materii prime de fiecare tip şi anume: posibila producere a produselor ÎN este definit pentru , adică găsim

Prin urmare, vectorul trebuie exclus din bază R 4 cu alte cuvinte, lansarea produsului ÎN limitat de materiile prime de tip I de care dispune intreprinderea. Luând în considerare volumele disponibile ale acestor materii prime, compania ar trebui să producă 8 produse ÎN. Numărul 9 este elementul de rezolvare și coloana vectorului P 2 și prima linie a tabelului. 7 sunt ghiduri. Alcătuim un tabel pentru iterația III (Tabelul 8).

Tabelul 8

În tabel 8, mai întâi completăm elementele din primul rând, care este rândul vectorului nou introdus în bază R 2 . Elementele acestui rând sunt obținute din elementele primului rând al tabelului. 7 prin împărțirea acestuia din urmă la elementul de rezoluție (adică la 9). Mai mult, în coloană C b din această linie scriem .

Apoi completăm elementele coloanelor vectorilor de bază și, folosind regula triunghiului, calculăm elementele coloanelor rămase. Ca urmare, în tabelul. 8 obținem un nou plan de referință X=(0; 8; 20; 0; 0; 96) și coeficienții de expansiune vectorială prin vectorii de bază și valorile corespunzătoare și

Verificăm dacă planul de referință dat este optim sau nu. Pentru a face acest lucru, luați în considerare a patra linie, tabelul. 8. Nu există numere negative printre numerele din această linie. Aceasta înseamnă că planul de referință găsit este optim și

Prin urmare, un plan de producție care include producția a 8 produse ÎNși 20 de produse CU, este optim. Cu acest plan pentru producția de produse, materiile prime de tipurile I și II sunt utilizate pe deplin și 96 kg de materii prime de tip III rămân neutilizate, iar costul produselor produse este de 400 de ruble.

Planul optim de producție nu prevede fabricarea produselor A. Introducere în planul de producție pentru produse de acest tip A ar duce la o reducere a costului total declarat. Acest lucru poate fi văzut din al 4-lea rând al coloanei vectoriale P 1, unde numărul 5 arată că pentru un anumit plan, inclusiv lansarea unei unități de produs A duce doar la o scădere a costului total cu 5 ruble.

Acest exemplu ar putea fi rezolvat folosind metoda simplex folosind un singur tabel (Tabelul 9). În acest tabel, toate cele trei iterații ale procesului de calcul sunt înregistrate secvenţial, una după alta.

Tabelul 9

După cum se vede din tabel. 10, planul de referință original nu este optim. Prin urmare, trecem la un nou plan de referință. Acest lucru se poate face deoarece în coloanele de vectori P 1 și p 5, al cărui rând al 4-lea conține numere negative, are elemente pozitive. Pentru a trece la un nou plan de referință, introducem vectorul în bază p 5 și excludeți vectorul din bază p 4 . Compunem tabelul II de iterație.

Tabelul 11

După cum se vede din tabel. 11, noul plan de referință al problemei nu este optim, deoarece în al 4-lea rând al coloanei vectoriale P 1 valorează un număr negativ -11/3. Deoarece nu există elemente pozitive în coloana acestui vector, această problemă nu are un plan optim.