Construcția unui tabel simplex. Metoda simplex pentru rezolvarea problemelor de programare liniară
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ă 
în orice caz.
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 unor egalităţi sau inegalităţi 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ă fiți capabil să reduceți 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ă-linie, 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.
pasul 1. 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.
|
Variabile |
Variabile de bază și suplimentare |
membri liberi (soluţie) |
Estimată atitudine |
|||||||
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 is 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.
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 rezolvare există un element de rezoluție a gs.
al 5-lea pas. Să construim următorul tabel. Pentru aceasta
Să trecem la pasul al treilea.
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
11.4. METODA DUAL SIMPLEX
Din rezultatele paragrafelor anterioare rezultă că pentru a obține o soluție la problema inițială, se poate trece la cea duală și, folosind estimări ale planului său optim, se poate determina soluția optimă a problemei inițiale.
Trecerea la problema duală nu este necesară, deoarece dacă luăm în considerare primul tabel simplex cu o bază suplimentară unitară, este ușor de observat că problema inițială este scrisă în coloane, iar cea duală este scrisă în rânduri.
După cum sa arătat, la rezolvarea unei probleme directe la orice iterație, diferența, adică magnitudinea -coeficientul variabilei, este egală cu diferența dintre partea dreaptă și stângă a constrângerii corespunzătoare problemei duale. Dacă, la rezolvarea unei probleme directe cu o funcție obiectiv maximizată, iterația nu conduce la o soluție optimă, atunci cel puțin pentru o variabilă și numai la optim pentru toate diferență .
Având în vedere această condiție ținând cont de dualitate, putem scrie
.
Astfel, dacă, Acea . Aceasta înseamnă că atunci când soluția problemei directe este suboptimă, soluția problemei duale nu este fezabilă. Pe cealaltă parte 
la . Rezultă că soluția optimă a problemei directe corespunde unei soluții admisibile a problemei duale.
Acest lucru a făcut posibilă dezvoltarea unei noi metode de rezolvare a problemelor de programare liniară, care produce mai întâi o soluție inacceptabilă, dar „mai bună decât optimă” (în metoda simplex obișnuită, se găsește mai întâi acceptabil, Dar suboptimal soluţie). Noua metodă, numită metoda dual simplex, asigură îndeplinirea condiţiilor pentru optimitatea soluţiei şi „aproximarea” sistematică a acesteia de regiunea soluţiilor fezabile. Când soluția rezultată se dovedește a fi fezabilă, procesul iterativ de calcule se încheie, deoarece această soluție este și optimă.
Metoda dual simplex face posibilă rezolvarea problemelor de programare liniară ale căror sisteme de constrângeri, cu o bază pozitivă, conțin termeni liberi de orice semn. Această metodă vă permite să reduceți numărul de transformări ale sistemului de constrângeri, precum și dimensiunea tabelului simplex. Să luăm în considerare aplicarea metodei dual simplex folosind un exemplu.
Exemplu. Găsiți minimul unei funcții 
sub restricții
.
Să trecem la forma canonică:
sub restricții
Tabelul inițial simplex are forma
|
De bază variabile |
X 1 |
X 2 |
X 3 |
X 4 |
X 5 |
Soluţie |
|
X 3 X 4 X 5 |
–3 –4 |
–1 –3 |
–3 –6 |
|||
|
–2 |
–1 |
Soluție de bază inițialăoptim, dar inacceptabil.
La fel ca metoda obișnuită simplex, metoda soluției luată în considerare se bazează pe utilizarea condițiilor de admisibilitate și optimitate.
Condiție de valabilitate. Cea mai mare variabilă de bază negativă în valoare absolută este selectată ca variabilă exclusă (dacă există alternative, alegerea se face în mod arbitrar). Dacă toate variabilele de bază sunt nenegative, procesul de calcul se încheie, deoarece soluția rezultată este fezabilă și optimă.
Condiție optimitatea. Variabila inclusă în bază este selectată dintre variabilele care nu sunt de bază, după cum urmează. Se calculează rapoartele coeficienților din stânga-ecuații la coeficienții corespunzători ai ecuației asociate cu variabila exclusă. Nu se iau în considerare rapoartele cu numitor pozitiv sau zero. În problema de minimizare, variabila de intrare trebuie să corespundă celui mai mic dintre rapoartele specificate, iar în problema de maximizare, raportul care este cel mai mic în valoare absolută (dacă există alternative, alegerea se face arbitrar). Dacă numitorii tuturor rapoartelor sunt zero sau pozitivi, problema nu are soluții fezabile.
După selectarea variabilelor care urmează să fie incluse în bază și excluse, pentru a obține următoarea soluție, se efectuează operația obișnuită de conversie a rândurilor unui tabel simplex.
În acest exemplu, variabila exclusă este. Rapoartele calculate pentru determinarea noii variabile de bază sunt date în următorul tabel:
|
Variabile |
X 1 |
X 2 |
X 3 |
X 4 |
X 5 |
|
Ecuația X 4 - ecuație |
–2 –4 |
–1 –3 |
|||
|
Atitudine |
Variabila inclusă este selectată X 2. Conversia ulterioară a șirurilor are ca rezultat un nou tabel simplex:
|
De bază variabile |
X 1 |
X 2 |
X 3 |
X 4 |
X 5 |
Soluţie |
|
X 3 X 2 X 5 |
–1 –1 |
|||||
Soluție nouă de asemenea, optim, dar încă inacceptabil. Ca o nouă variabilă exclusă alegem (arbitrar) X 3. Să definim variabila care trebuie inclusă.
|
Variabile |
X 1 |
X 2 |
X 3 |
X 4 |
X 5 |
|
Ecuația X 4 - ecuație |
|||||
|
atitudine |
Una dintre metodele de rezolvare a problemelor de optimizare ( asociată de obicei cu găsirea minimului sau maximului) programarea liniară se numește . Metoda simplex include un întreg grup de algoritmi și metode pentru rezolvarea problemelor de programare liniară. Una dintre aceste metode, care presupune înregistrarea datelor sursă și recalcularea lor într-un tabel special, se numește metoda tabulară simplex.
Să luăm în considerare algoritmul metodei simplex tabulare folosind exemplul soluției sarcina de productie, care se rezumă la găsirea unui plan de producție care să asigure profit maxim.
Date de intrare pentru problema metodei simplex
Compania produce 4 tipuri de produse, prelucrandu-le pe 3 masini.
Standardele de timp (min./buc) pentru prelucrarea produselor pe mașini sunt specificate de matricea A:
Fondul de timp de funcționare a mașinii (min.) este specificat în matricea B:
Profitul din vânzarea fiecărei unități de produs (RUB/buc) este dat de matricea C:
Scopul sarcinii de producție
Întocmește un plan de producție care să maximizeze profitul întreprinderii.
Rezolvarea problemei folosind metoda simplex tabelar
(1) Să notăm cu X1, X2, X3, X4 numărul planificat de produse de fiecare tip. Apoi planul dorit: ( X1, X2, X3, X4)
(2) Să notăm constrângerile planului sub forma unui sistem de ecuații:
(3) Atunci profitul tinta este:
Adică, profitul din îndeplinirea planului de producție ar trebui să fie maxim.
(4) Pentru a rezolva problema extremului condiționat rezultat, înlocuim sistemul de inegalități cu un sistem de ecuații liniare prin introducerea unor variabile suplimentare nenegative în el ( X5, X6, X7).
(5) Să acceptăm următoarele plan de referință:
X1 = 0, X2 = 0, X3 = 0, X4 = 0, X5 = 252, X6 = 144, X7 = 80
(6) Să introducem datele în tabel simplex:
În ultima linie introducem coeficienții funcției obiectiv și valoarea acesteia însăși cu semnul opus;
(7) Selectați în ultima linie cel mai mare (modulo) un număr negativ.
Să calculăm b = N / Elemente_din_coloana_selectată
Dintre valorile calculate ale lui b alegem cel mai puţin.
Intersecția coloanei și rândului selectate ne va oferi elementul de rezolvare. Schimbăm baza într-o variabilă corespunzătoare elementului de rezolvare ( X5 la X1).
- Elementul de rezolvare în sine se transformă în 1.
- Pentru elementele liniei de rezoluție – a ij (*) = a ij / RE ( adică împărțim fiecare element la valoarea elementului de rezoluție și obținem date noi).
- Pentru elementele coloanei de rezoluție, acestea sunt pur și simplu resetate la zero.
- Recalculăm elementele rămase ale tabelului folosind regula dreptunghiului.
a ij (*) = a ij – (A * B / RE)
După cum puteți vedea, luăm celula curentă care este recalculată și celula cu elementul de rezolvare. Ele formează colțuri opuse ale dreptunghiului. Apoi, înmulțim valorile din celulele celorlalte 2 colțuri ale acestui dreptunghi. Acest lucru ( A * B) împărțire la elementul de rezolvare ( RE). Și scade din celula curentă care este recalculată ( a ij) Ce s-a întâmplat. Obținem o nouă valoare - a ij (*).
(9) Verificați din nou ultima linie ( c) pe prezența numerelor negative. Dacă nu sunt acolo, a fost găsit planul optim, trecem la ultima etapă de rezolvare a problemei. Dacă există, planul nu este încă optim și tabelul simplex trebuie recalculat din nou.
Deoarece avem din nou numere negative în ultima linie, începem o nouă iterație de calcule.
(10) Deoarece nu există elemente negative în ultima linie, asta înseamnă că am găsit planul optim de producție! Și anume: vom produce acele produse care s-au mutat în coloana „Base” - X1 și X2. Cunoaștem profitul din producția fiecărei unități de producție ( matricea C). Rămâne să înmulțim volumele de producție găsite ale produselor 1 și 2 cu profit pe 1 bucată, obținem finalul ( maxim! ) profit pentru un plan de producție dat.
RĂSPUNS:
X1 = 32 buc., X2 = 20 buc., X3 = 0 buc., X4 = 0 buc.
P = 48 * 32 + 33 * 20 = 2.196 rub.
Galyautdinov R.R.
© Copierea materialului este permisă numai dacă există un hyperlink direct către
Dacă ați înțeles deja metoda grafică de rezolvare a problemelor de programare liniară, este timpul să treceți la metoda simplex. Spre deosebire de primul, practic nu are restricții asupra problemei (orice număr de variabile, semne diferite etc.) și se modifică în funcție de tipul problemei (de exemplu, metoda M sau metoda bazei artificiale).
Când se rezolvă o problemă folosind metoda simplex, calculele sunt de obicei efectuate (pentru compactitate și claritate) în tabele (metoda simplex tabelar), iar ultimul tabel cu soluția optimă conține informații suplimentare importante: soluția problemei duale, resursele rămase , informații despre resursele limitate etc. , care permite o analiză economică a unei probleme de programare liniară (vezi exemplul 3 de mai jos).
Exemple de soluții la probleme folosind metoda simplex sunt postate gratuit pentru confortul dvs. - studiați, căutați altele similare, rezolvați. Dacă aveți nevoie de ajutor cu sarcini ca aceasta, accesați: Soluție de programare liniară personalizată.
Rezolvarea problemelor folosind metoda simplex: exemple online
Sarcina 1. Compania produce rafturi pentru baie în două dimensiuni - A și B. Agenții de vânzări estimează că pe piață ar putea fi vândute până la 550 de rafturi pe săptămână. Fiecare raft de tip A necesită 2 m2 de material, iar fiecare raft de tip B necesită 3 m2 de material. Compania poate primi până la 1200 m2 de material pe săptămână. Pentru fabricarea unui raft de tip A sunt necesare 12 minute de timp de mașină, iar pentru fabricarea unui raft de tip B - 30 de minute; Aparatul poate fi folosit 160 de ore pe săptămână. Dacă profitul din vânzarea de rafturi de tip A este de 3 unități monetare, iar din rafturi de tip B - 4 unități monetare. unități, atunci câte rafturi de fiecare tip ar trebui să fie produse pe săptămână?
Întocmirea unui model matematic și rezolvarea ZLP folosind metoda simplex (pdf, 33 Kb)
Sarcina 2. Rezolvați o problemă de programare liniară folosind metoda simplex. 
Soluție folosind metoda simplex pe bază artificială (pdf, 45 Kb)
Sarcina 3. Compania produce 3 tipuri de produse: A1, A2, A3, folosind două tipuri de materii prime. Sunt cunoscute costurile fiecărui tip de materie primă pe unitate de producție, rezervele de materii prime pentru perioada de planificare, precum și profitul dintr-o unitate de producție de fiecare tip.
- Câte articole de fiecare tip trebuie produse pentru a maximiza profitul?
- Determinați starea fiecărui tip de materie primă și valoarea sa specifică.
- Să se determine intervalul maxim de modificare a stocurilor pentru fiecare tip de materie primă, în cadrul căruia structura planului optim, i.e. Nomenclatura de producție nu se va modifica.
- Determinați cantitatea de produse produse și profitul din producție atunci când creșteți stocul unuia dintre tipurile rare de materii prime la valoarea maximă posibilă (în intervalul dat de producție).
- Determinați intervalele de modificare a profitului dintr-o unitate de producție de fiecare tip la care planul optim rezultat nu se va modifica.
Rezolvarea unei probleme de programare liniară cu analiză economică (pdf, 163 Kb)
Sarcina 4. Rezolvați o problemă de programare liniară folosind metoda simplex: 
Rezolvare folosind metoda tabelar simplex cu căutarea planului de referință (pdf, 44 Kb)
Sarcina 5. Rezolvați o problemă de programare liniară folosind metoda simplex: 
Rezolvare folosind metoda tabulară simplex (pdf, 47 Kb)
Sarcina 6. Rezolvați problema folosind metoda simplex, considerând ca plan de referință inițial planul dat în condiția: 
Rezolvare prin metoda manuală simplex (pdf, 60 Kb)
Sarcina 7. Rezolvați problema folosind metoda simplex modificată.
Pentru a produce două tipuri de produse A și B, se folosesc trei tipuri de echipamente tehnologice. Pentru a produce o unitate de produs A, echipamentele de primul tip folosesc a1=4 ore, echipamente de al doilea tip a2=8 ore, iar echipamentele de al treilea tip a3=9 ore. Pentru a produce o unitate de produs B, echipamentele de primul tip folosesc b1=7 ore, echipamente de al doilea tip b2=3 ore, iar echipamentele de al treilea tip b3=5 ore.
Echipamentele de primul tip pot lucra pentru producerea acestor produse timp de cel mult t1=49 ore, echipamentele de al doilea tip nu mai mult de t2=51 ore, echipamentele de al treilea tip nu mai mult de t3=45 de ore.
Profitul din vânzarea unei unități de produs finit A este ALPHA = 6 ruble, iar produsul B este BETTA = 5 ruble.
Întocmește un plan de producție a produselor A și B, asigurând profit maxim din vânzarea acestora.
Soluție folosind metoda simplex modificată (pdf, 67 Kb)
Sarcina 8. Găsiți soluția optimă folosind metoda dual simplex 
Soluție folosind metoda dual simplex (pdf, 43 Kb)
Exemple de soluții la probleme de programare liniară
Metode de rezolvare a problemelor de programare liniară
Soluții de referință la o problemă de programare liniară
Să fie dată o problemă de programare liniară în notație canonică
in conditii
Vom nota prin setul de soluții sisteme (2) – (3). Să presupunem că , unde este rangul matricei și este numărul de ecuații din sistemul (2).
Din sistemul de vectori coloană ai matricei, selectăm un subsistem de vectori liniar independent. Există pentru că . Acest sistem formează o bază în . Să notăm prin , . Hai sa sunăm set de valori de bază index, – submatrice de bază matrici Vom numi coordonatele vectorului de bază , dacă nebază in caz contrar.
Să scriem sistemul (2) sub forma . Să împărțim termenii din partea stângă în de bază și nebază, adică
Să definim o soluție particulară a acestui sistem după cum urmează. Să setăm toate variabilele care nu sunt de bază egale cu zero în (4). Apoi sistemul (4) va lua forma
Să sunăm (5) subsistem de bază sistem de ecuații (2). Să notăm cu un vector compus din coordonatele de bază ale vectorului . Apoi sistemul (2) poate fi rescris sub formă de matrice vectorială
Deoarece submatricea este de bază, aceasta
nedegenerat. Prin urmare, sistemul (6) are o soluție unică. Se va numi soluţia particulară a sistemului (2) obţinută în acest fel soluție de referință problema de programare liniară directă corespunzătoare bazei. (Uneori soluția de referință este numită și de bază ). După cum putem vedea, baza corespunde unei singure soluții de suport. Evident, numărul de soluții de suport este finit.
Pentru această bază, determinăm și soluția de referință pentru problema de programare liniară duală. Amintiți-vă că problema duală cu cea canonică are forma
in conditii
Să scriem sistemul (8) sub forma
Reamintim că setul de soluții ale sistemului (8) este notat cu .
Să definim vectorul variabilelor duale din condiția îndeplinirii constrângerilor de bază din sistemul (9) ca egalități. Obținem următorul sistem de ecuații liniare:
Să notăm printr-un vector compus din ba-
coordonatele zis ale vectorului. Apoi sistemul (10) poate fi rescris sub formă de matrice vectorială
Sistemul (11) are și o soluție unică.
Să-l sunăm de sprijin (de bază )decizie problema de programare liniară duală corespunzătoare bazei. Această soluție de referință este, de asemenea, determinată în mod unic.
Deci, orice bază corespunde la doi vectori - două soluții de referință la problemele de programare liniară directă și, respectiv, duală.
Să definim în continuare următoarele tipuri de baze și soluții de sprijin. Dacă toate coordonatele soluției suport sunt nenegative, atunci se numește baza căreia îi corespunde această soluție suport acceptabil plan de referință problema de programare liniară directă și se numește soluția de referință corespunzătoare aceleiași baze pseudoplan dubla problema. De fapt, pentru ca baza să fie admisibilă, este suficientă nenegativitatea coordonatelor bazei. Rețineți că planul de referință este un vector fezabil al problemei de programare liniară înainte ().
Dacă soluția de referință satisface toate restricțiile (9) ale problemei duale, atunci baza căreia îi corespunde această soluție de referință se numește dublu valabil . În acest caz, vectorul este numit plan de referință problema de programare liniară duală și soluția de referință corespunzătoare aceleiași baze
se numeste pseudoplan sarcină directă.
Pentru admisibilitatea dublă a unei baze, este suficient să se satisfacă numai inegalitățile nebazice. Rețineți că planul de referință este un vector fezabil al problemei de programare liniară duală ().
Notăm diferențele dintre laturile stânga și dreapta ale inegalităților (9) prin , . Apoi admisibilitatea duală a unui temei poate fi stabilită prin verificarea nenegativității tuturor . Rețineți că, după cum rezultă direct din definiție, toate reziduurile de bază sunt egale cu zero ().
Un exemplu de rezolvare a unei probleme directe și duale folosind metoda simplex
Prin urmare, este suficient să ne asigurăm că inegalitățile sunt valabile pentru toată lumea.
Teorema 1. LăsaȘi– soluții de referință ale problemei de programare liniară corespunzătoare unei anumite baze, atunci egalitatea este valabilă .
Dovada . Din definițiile soluțiilor suport se obține ușor egalitățile
deci urmează validitatea teoremei.
Teorema 2. (Criteriul de optimizare pentru soluțiile de suport) Dacă bazăeste simultan admisibil și dual admisibil, apoi soluțiile de sprijin corespunzătoareȘisunt soluții, respectiv, ale problemelor de programare liniară directă și duală.
Dovada. Valabilitatea acestei afirmații rezultă din teoria dualității în programarea liniară și din Teorema 1.
Teorema 3. O soluție admisibilă a problemei (1) – (3) este un plan de referință al problemei dacă și numai dacă este vârful unei mulțimi poliedrice convexe.
Dovada. Lăsa – planul de referință al problemei (1) – (3). Să demonstrăm asta – partea de sus a setului . Prin definiție, un plan de referință – soluţie de referinţă admisibilă corespunzătoare unei anumite baze, adică – rezolvarea unui sistem de ecuații liniare în raport cu variabile
Este ușor de observat că acest sistem are o soluție unică. Aceasta înseamnă că planul de sprijin al feței care conține punctul , are dimensiunea 0. Prin urmare, – partea de sus a setului .
Înapoi. Lăsa – partea de sus a setului. Să demonstrăm asta – planul de referință al problemei (1) – (3). Deoarece este un vârf, este o față a mulțimii a cărei dimensiune este zero. Prin urmare, vectorul există cel puțin zero componente, a căror mulțime de numere o notăm . Prin urmare, – singura soluție pentru sistem
Unde . Prin urmare, rămâne de demonstrat că sistemul de vectori este liniar independent. Să presupunem contrariul. Apoi există numere care nu sunt toate egale cu zero, astfel încât . De aceea
Aceasta înseamnă că sistemul (12) are o soluție diferită de , ceea ce contrazice unicitatea soluției sale. Astfel, este baza și vectorul – planul de referință corespunzător problemei (1) – (3). Asta se cerea.
Rețineți că o soluție admisibilă la problema (7), (8) (problema duală (1) – (3)) este, de asemenea, un plan de sprijin dacă și numai dacă este vârful mulțimii admisibile.
Data publicării: 2015-01-10; Citește: 695 | Încălcarea drepturilor de autor ale paginii
Studopedia.org - Studopedia.Org - 2014-2018 (0,005 s)...
Pentru certitudine, presupunem că problema care se rezolvă este găsirea minimului.
1. Reduceți problema de programare liniară la formă canonică.
După introducerea unor variabile suplimentare, scriem sistemul de ecuații și funcția liniară într-o formă numită sistem extins:
Presupunem că toate variabilele suplimentare au același semn ca și termenii liberi; altfel folosim așa-numitul M– o metodă care va fi discutată mai jos.
2. Definiți variabilele de bază și libere.
3. Introducem sistemul original extins în primul simplex - tabel. Ultimul rând al tabelului, care oferă ecuația pentru funcția obiectiv liniară, este numit evaluare. Indică coeficienții funcției obiectiv. În coloana din stânga tabelului notăm principalele variabile (bază), în coloanele ulterioare notăm coeficienții pentru variabilele libere. Penultima coloană conține membri liberi ai sistemului extins. Ultima coloană este pregătită pentru relațiile de estimare necesare pentru determinarea variabilei de bază pe baza relației (6.29).
4. Determinați posibilitatea rezolvării problemei prin valori conform teoremelor 6.7,…, 6.9.
5. Selectați elementul de rezolvare (referință).
Rezolvarea unei probleme de producție folosind metoda simplex tabelar
Dacă nu este îndeplinit criteriul de optimitate (nu sunt îndeplinite condițiile teoremei 6.7 sau 6.8), atunci cel mai mare coeficient negativ absolut din ultimul rând determină coloana de rezoluție (referință). 
.
Compunem rapoartele estimate ale fiecărei linii conform următoarelor reguli:
1 0) dacă toate și au semne diferite;
2 0) dacă toate și ;
3 0) dacă ;
4 0) 0 dacă și ;
5 0) dacă și au aceleași semne.
Să definim. Dacă nu există un minim final, atunci problema nu are un optim final (). Dacă minimul este finit, atunci selectați linia q, pe care se realizează (oricare, dacă sunt mai multe), și numiți-o linia de rezolvare (de referință). La intersecția rândului și coloanei de rezolvare există un element de rezolvare (de referință).
6 0) Mergeți la următorul tabel conform regulilor:
a) în coloana din stânga scriem o nouă bază: în locul variabilei principale - o variabilă, i.e. Să schimbăm variabilele și ;
b) se pune 1 în locul elementului de susținere;
c) lăsați elementele tabelului inițial în locurile rămase ale rândului de referință din noul tabel;
d) în locurile rămase din coloana de referință, se pun elementele corespunzătoare din tabelul inițial, înmulțite cu –1;
e) pentru spațiile libere rămase ale elementelor , , în noul tabel, notați numerele , , , care se regăsesc astfel:
Pentru a simplifica calculele folosind aceste formule, acestea pot fi formulate ca „Reguli dreptunghiulare”(Fig. 6.8): se înmulțesc elementele de pe diagonalele unui dreptunghi cu vârfuri (sau , , , , sau , , , ) (produsul care nu conține elementul de susținere se ia cu semnul minus) și produsele rezultate sunt adăugat;
f) împărțiți toate elementele primite ale noului tabel la elementul de referință.
7 0) Folosind valoarea elementului, determinați dacă a fost găsită valoarea optimă a funcției obiectiv. Dacă răspunsul este negativ, continuați decizia (reveniți la punctul 6).
Orez. 6.8. Regula dreptunghiulară pentru determinarea numerelor:
a − , b − , c − .
Se consideră un algoritm de conversie a tabelelor simplex pentru soluții de bază admisibile nedegenerate, i.e. situaţia descrisă de teorema 6.9 a fost îndeplinită. Dacă problema inițială de programare liniară este degenerată, atunci în cursul rezolvării ei folosind metoda simplex, pot apărea soluții de bază degenerate. În acest caz, sunt posibili pașii inactivi ai metodei simplex, adică. iterații în care f(X) nu se schimba. Este posibilă și bucla, de exemplu o succesiune nesfârșită de pași inactiv. Pentru a o preveni, au fost dezvoltați algoritmi speciali - anticicline. Cu toate acestea, în majoritatea covârșitoare a cazurilor, pașii inactivi sunt înlocuiți cu pași cu o scădere a funcției obiectiv, iar procesul de rezolvare este finalizat ca urmare a unui număr finit de iterații.
Exemplul 6.8. Rezolvați problema dată în exemplul 6.7 folosind metoda simplex.
⇐ Anterior45678910111213Următorul ⇒
Data publicării: 23-01-2015; Citește: 174 | Încălcarea drepturilor de autor ale paginii
Studopedia.org - Studopedia.Org - 2014-2018 (0,002 s)...
Acasă >> Exemplul nr. 3. Metoda simplex. Găsirea celei mai mari valori a unei funcții (bază artificială)
Metoda simplex
| — | x 1 | + | x 2 | ≥ | 1 | |
| x 1 | + | 3 | x 2 | ≤ | 15 | |
| — | 2 | x 1 | + | x 2 | ≤ | 4 |
| O variabilă se numește bază pentru o anumită ecuație dacă este inclusă în această ecuație cu un coeficient de unu și nu este inclusă în ecuațiile rămase (cu condiția ca în partea dreaptă a ecuației să existe un număr pozitiv). Dacă fiecare ecuație are o variabilă de bază, atunci se spune că sistemul are o bază. Ideea metodei simplex este de a trece de la o bază la alta, obținând o valoare a funcției care este cel puțin nu mai mică decât cea existentă (fiecărei baze îi corespunde o singură valoare a funcției). Cum se realizează trecerea de la o bază la alta? |
| x 1 = 0 x 2 = 0 S 1 = 0 S 2 = 15 S 3 = 4 R 1 = 1 |
=> W = 1 |
| x 1 | x 2 | S 1 | S 2 | S 3 | R 1 | Sf. membru | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | 1: 1 = 1 |
| 1 | 3 | 0 | 1 | 0 | 0 | 15 | 15: 3 = 5 |
| -2 | 1 | 0 | 0 | 1 | 0 | 4 | 4: 1 = 4 |
| 1 | -1 | 1 | 0 | 0 | 0 | W - 1 | |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | |
| 4 | 0 | 3 | 1 | 0 | -3 | 12 | |
| -1 | 0 | 1 | 0 | 1 | -1 | 3 | |
| 0 | 0 | 0 | 0 | 0 | 1 | W - 0 |
| x 1 | x 2 | S 1 | S 2 | S 3 | Sf. membru | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 4 | 0 | 3 | 1 | 0 | 12 | 12: 4 = 3 |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | F - 1 | |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | F - 1 | |
| 0 | 1 | -1/4 | 1/4 | 0 | 4 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| 0 | 0 | 7/4 | 1/4 | 1 | 6 | |
| 0 | 0 | -2 | -1 | 0 | F - 13 |
| S 1 = 0 S 2 = 0 x 1 = 3 x 2 = 4 S 3 = 6 |
=> F - 13 = 0 => F = 13 |
Nu există coeficienți pozitivi printre coeficienții rândului selectați. În consecință, s-a găsit cea mai mare valoare a funcției F.
Răspuns:
x 1 = 3 x 2 = 4
F max = 13
Mergeți la soluția problemei dvs
© 2010-2018, pentru orice întrebări vă rugăm să scrieți la [email protected]
Sarcina
Pentru a vinde trei grupe de bunuri, o întreprindere comercială are trei tipuri de resurse materiale și monetare limitate în valoare de b 1 = 240, b 2 = 200, b 3 = 160 de unități. În același timp, pentru vânzarea unui grup de mărfuri pentru 1 mie de ruble. cifra de afaceri a mărfurilor, resursa de primul tip este consumată în valoare de 11 = 2 unități, resursa de al doilea tip în valoare de 21 = 4 unități, resursa de al treilea tip în valoare de 31 = 4 unitati. Pentru vânzarea a 2 și 3 grupuri de mărfuri pentru 1 mie de ruble. cifra de afaceri se consumă în funcție de resursa primului tip în valoare de a 12 = 3, a 13 = 6 unități, resursa de al doilea tip în cantitate de a 22 = 2, a 23 = 4 unități, resursa de al treilea tip în valoare de a 32 = 6, a 33 = 8 unități . Profit din vânzarea a trei grupe de mărfuri la 1 mie.
Metoda simplex pentru rezolvarea ZLP
freca. cifra de afaceri este respectiv c 1 = 4, c 2 = 5, c 3 = 4 (mii de ruble). Determinați volumul planificat și structura cifrei de afaceri comerciale astfel încât profitul întreprinderii comerciale să fie maximizat.
La problema directă a planificării cifrei de afaceri, rezolvate prin metoda simplex, Compune dubla problema programare liniară.
Instalare perechi conjugate de variabile probleme directe și duble.
După perechi conjugate de variabile, din soluția problemei directe obținem rezolvarea problemei duale, în care este produs evaluarea resurselor, cheltuită pentru vânzarea de bunuri.
Rezolvarea problemei folosind metoda simplex
Fie x 1, x 2, x 3 numărul de mărfuri vândute, în mii de ruble, 1, 2, 3 - grupele ei, respectiv. Atunci modelul matematic al problemei are forma:
F = 4 x 1 + 5 x 2 + 4 x 3 ->max
Rezolvăm metoda simplex.
Introducem variabile suplimentare x 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0 pentru a transforma inegalitățile în egalități.
Să luăm ca bază x 4 = 240; x 5 = 200; x 6 = 160.
Introducem datele în tabel simplex
Tabel simplex nr. 1
Funcție obiectivă:
0 240 + 0 200 + 0 160 = 0
Calculăm estimări folosind formula:
Δ 1 = 0 2 + 0 4 + 0 4 - 4 = - 4
Δ 2 = 0 3 + 0 2 + 0 6 - 5 = - 5
Δ 3 = 0 6 + 0 4 + 0 8 - 4 = - 4
Δ 4 = 0 1 + 0 0 + 0 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 0 0 - 0 = 0
Δ 6 = 0 0 + 0 0 + 0 1 - 0 = 0
Deoarece există estimări negative, planul nu este optim. Cel mai mic scor:
Introducem variabila x 2 în bază.
Definim o variabilă care reiese din bază. Pentru a face acest lucru, găsim cel mai mic raport nenegativ pentru coloana x2.
= 26.667
Cel mai mic nenegativ: Q 3 = 26,667. Deducem variabila x 6 din bază
Împărțiți a treia linie la 6.
Din prima linie, scădeți a treia linie, înmulțită cu 3
Din a doua linie, scădeți a treia linie, înmulțită cu 2
Calculam:
Primim un tabel nou:
Tabel simplex nr. 2
Funcție obiectivă:
0 160 + 0 440/3 + 5 80/3 = 400/3
Calculăm estimări folosind formula:
Δ 1 = 0 0 + 0 8/3 + 5 2/3 - 4 = - 2/3
Δ 2 = 0 0 + 0 0 + 5 1 - 5 = 0
Δ 3 = 0 2 + 0 4/3 + 5 4/3 - 4 = 8/3
Δ 4 = 0 1 + 0 0 + 5 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 5 0 - 0 = 0
Δ 6 = 0 (-1)/2 + 0 (-1)/3 + 5 1/6 - 0 = 5/6
Deoarece există o estimare negativă Δ 1 = - 2/3, planul nu este optim.
Introducem variabila x 1 în bază.
Definim o variabilă care reiese din bază. Pentru a face acest lucru, găsim cel mai mic raport nenegativ pentru coloana x 1.
Cel mai mic nenegativ: Q 3 = 40. Deducem variabila x 2 din bază
Împărțiți a treia linie la 2/3.
Din a 2-a linie, scădeți a 3-a linie, înmulțită cu 8/3
Calculam:
Primim un tabel nou:
Tabel simplex nr. 3
Funcție obiectivă:
0 160 + 0 40 + 4 40 = 160
Calculăm estimări folosind formula:
Δ 1 = 0 0 + 0 0 + 4 1 - 4 = 0
Δ 2 = 0 0 + 0 (-4) + 4 3/2 - 5 = 1
Δ 3 = 0 2 + 0 (-4) + 4 2 - 4 = 4
Δ 4 = 0 1 + 0 0 + 4 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 4 0 - 0 = 0
Δ 6 = 0 (-1)/2 + 0 (-1) + 4 1/4 - 0 = 1
Deoarece nu există evaluări negative, planul este optim.
Rezolvarea problemei:
Răspuns
x 1 = 40; x2 = 0; x 3 = 0; x 4 = 160; x 5 = 40; x6 = 0; F max = 160
Adică, este necesar să se vinde primul tip de mărfuri în valoare de 40 de mii.
freca. Produsele de tipurile 2 și 3 nu trebuie vândute. În acest caz, profitul maxim va fi F max = 160 de mii de ruble.
Rezolvarea problemei duale
Problema duală are forma:
Z = 240 y 1 + 200 y 2 + 160 y 3 ->min
Introducem variabile suplimentare y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0 pentru a transforma inegalitățile în egalități.
Perechile conjugate de variabile ale problemelor directe și duale au forma:
Din ultimul tabel simplex nr. 3 al problemei directe, găsim soluția problemei duale:
Z min = F max = 160;
y 1 = Δ 4 = 0; y 2 = Δ 5 = 0; y 3 = Δ 6 = 1; y 4 = Δ 1 = 0; y5 = Δ2 = 1; y 6 = Δ 3 = 4;
Răspuns
y 1 = 0; y2 = 0; y 3 = 1; Z min = 160;
Metoda simplex este o procedură de calcul bazată pe principiul îmbunătățirii secvențiale a soluțiilor la trecerea de la un punct de bază (soluție de bază) la altul. În acest caz, valoarea funcției obiectiv se îmbunătățește.
Soluția de bază este una dintre soluțiile admisibile situate la vârfurile regiunii valorilor admisibile. Prin verificarea optimității vârf după vârf al simplexului, se ajunge la optimul dorit. Metoda simplex se bazează pe acest principiu.
Un simplex este un poligon convex în spațiu n-dimensional cu n+1 vârfuri care nu se află în același hiperplan (hiperplanul împarte spațiul în două semi-spații).
De exemplu, linia constrângerilor bugetare împarte bunurile în disponibile și indisponibile.
S-a dovedit că, dacă există o soluție optimă, atunci cu siguranță va fi găsită după un număr finit de iterații (pași), cu excepția cazurilor de „ciclare”.
Algoritmul metodei simplex constă dintr-un număr de etape.
Primul stagiu. Se construiește un model inițial de optimizare. În continuare, matricea originală de condiții este transformată în forma canonică redusă, care, printre toate celelalte forme canonice, se distinge prin faptul că:
a) partea dreaptă a condițiilor (termeni liberi bi) sunt cantități nenegative;
b) condiţiile în sine sunt egalităţi;
c) matricea de condiții conține o submatrice unitară completă.
Dacă termenii liberi sunt negativi, atunci ambele părți ale inegalității sunt înmulțite cu - 1, iar semnul inegalității este inversat. Pentru a transforma inegalitățile în egalități, se introduc variabile suplimentare, care indică de obicei cantitatea de resurse subutilizate. Acesta este sensul lor economic.
În sfârșit, dacă, după adăugarea unor variabile suplimentare, matricea de condiții nu conține o submatrice de identitate completă, atunci se introduc variabile artificiale care nu au niciun sens economic. Ele sunt introduse numai pentru a obține submatricea de identitate și pentru a începe procesul de rezolvare a problemei folosind metoda simplex.
Într-o soluție optimă a problemei, toate variabilele artificiale (AI) trebuie să fie egale cu zero. Pentru a face acest lucru, în funcția obiectiv a problemei sunt introduse variabile artificiale cu coeficienți negativi mari (-M) la rezolvarea problemei la max, și cu coeficienți pozitivi mari (+M) când problema este rezolvată la min. În acest caz, chiar și o valoare nesemnificativă diferită de zero a variabilei artificiale va scădea (mărește) brusc valoarea funcției obiectiv. De obicei, M ar trebui să fie de 1000 de ori mai mare decât valorile coeficienților pentru variabilele principale.
Faza a doua. Se construiește un tabel inițial simplex și se găsește o soluție de bază inițială. Setul de variabile care formează submatricea identității este luat ca soluție de bază inițială. Valorile acestor variabile sunt egale cu termenii liberi. Toate celelalte variabile în afara bazei sunt zero.
A treia etapă. Verificarea optimității soluției de bază se realizează folosind estimări speciale ale coeficienților funcției obiectiv. Dacă toate estimările coeficienților funcției obiectiv sunt negative sau egale cu zero, atunci soluția de bază existentă este optimă. Dacă cel puțin o estimare a coeficientului funcției obiectiv este mai mare decât zero, atunci soluția de bază existentă nu este optimă și trebuie îmbunătățită.
Etapa a patra. Trecerea la o nouă soluție de bază. Evident, planul optim ar trebui să includă o variabilă care mărește funcția obiectiv în cea mai mare măsură. La rezolvarea problemelor pentru profit maxim, planul optim include produse a căror producție este cea mai profitabilă. Aceasta este determinată de valoarea maximă pozitivă a estimării coeficientului funcției obiectiv.
Coloana tabelului simplex cu acest număr la această iterație se numește coloană generală.
Pentru a găsi rândul general, toți membrii liberi (resurse) sunt împărțiți în elementele corespunzătoare ale coloanei generale (rata de consum de resurse pe unitate de produs). Cel mai mic este selectat din rezultatele obținute. Linia corespunzătoare la o iterație dată se numește linie generală. Ea corespunde resursei care limitează producția la o anumită iterație.
Un element al unui tabel simplex situat la intersecția unei coloane generale și a unui rând se numește element general.
Apoi toate elementele șirului general (inclusiv membrul liber) sunt împărțite în elementul general. Ca urmare a acestei operații, elementul general devine egal cu unu. În continuare, este necesar ca toate celelalte elemente ale coloanei generale să devină egale cu zero, adică. coloana generală ar trebui să devină unică. Toate liniile (cu excepția celei generale) sunt convertite după cum urmează. Elementele rezultate ale noului rând sunt înmulțite cu elementul corespunzător al coloanei generale și produsul rezultat este scăzut din elementele rândului vechi.
Obținem valorile noilor variabile de bază în celulele corespunzătoare ale coloanei de termeni liberi.
Etapa a cincea. Soluția de bază rezultată este verificată pentru optimitatea (vezi a treia etapă). Dacă este optim, atunci calculele se opresc. În caz contrar, este necesar să se găsească o nouă soluție de bază (etapa a patra), etc.
Metoda simplex
Un exemplu de rezolvare a problemelor de optimizare a programării liniare folosind metoda simplex
Să fie necesar să găsim planul optim de producție pentru două tipuri de produse (x1 și x2).
Date inițiale:
Să construim un model de optimizare
– limitarea resurselor A;
– limitarea resurselor B.
Să reducem problema la forma canonică redusă. Pentru a face acest lucru, este suficient să introduceți variabile suplimentare X3 și X4. Ca urmare, inegalitățile sunt transformate în egalități stricte.
Să construim tabelul simplex inițial și să găsim soluția de bază inițială. Acestea vor fi variabile suplimentare, deoarece corespund unei submatrici de unitate.
Prima iterație. Găsiți coloana generală și rândul general:
Elementul general este 5.
a 2-a iterație. Soluția de bază găsită nu este optimă, deoarece linia de rating (Fj-Cj) conține un element pozitiv. Găsiți coloana generală și rândul general:
max(0,0,3,-1,4,0) = 0,2
Soluția găsită este optimă, deoarece toate estimările speciale ale funcției obiectiv Fj – Cj sunt egale cu zero sau negative. F(x)=29 x1=2; x2=5.
Probleme de programare liniară. Este într-o construcție secvențială care caracterizează procesul luat în considerare. Soluția este împărțită în trei etape principale: selecția variabilelor, construirea unui sistem de constrângeri și căutarea unei funcții obiective.
Pe baza acestei împărțiri, condiția problemei poate fi reformulată astfel: extremul funcției obiectiv Z(X) = f(x1, x2, … ,xn) → max (min) și variabilele corespunzătoare, dacă se știe că acestea satisface sistemul de constrângeri: Φ_i ( x1, x2, … ,xn) = 0 pentru i = 1, 2, …, k;Φ_i (x1, x2, … ,xn)) 0 pentru i = k+1, k+ 2, …, m.
Sistemul de restricții trebuie adus la o formă canonică, adică. la un sistem de ecuații liniare, unde numărul de variabile este mai mare decât numărul de ecuații (m > k). În acest sistem vor exista cu siguranță variabile care pot fi exprimate prin alte variabile, iar dacă nu este cazul, atunci ele pot fi introduse artificial. În acest caz, primele sunt numite bază sau bază artificială, iar cele din urmă sunt numite libere.
Este mai convenabil să luați în considerare metoda simplex folosind un exemplu specific. Să fie dată o funcție liniară f(x) = 6x1 + 5x2 + 9x3 și un sistem de constrângeri: 5x1 + 2x2 + 3x3 ≤ 25 x1 + 6x2 + 2x3 ≤ 20 valoarea funcţiei f(x).
Rezolvare În prima etapă, specificați soluția inițială (de referință) a sistemului de ecuații într-un mod absolut arbitrar, care trebuie să satisfacă sistemul de constrângeri dat. În acest caz, este necesară introducerea artificială, adică. variabilele de bază x4, x5 și x6 după cum urmează: 5x1 + 2x2 + 3x3 + x4 = 25 x1 + 6x2 + 2x3 + x5 = 4x1 + 3x3 + x6 = 18;
După cum puteți vedea, inegalitățile au fost transformate în egalități datorită variabilelor adăugate x4, x5, x6, care sunt cantități nenegative. Astfel, ați adus sistemul la forma sa canonică. Variabila x4 este inclusă în prima ecuație cu un coeficient de 1, iar în a doua ecuație cu un coeficient de 0, același lucru este valabil și pentru variabilele x5, x6 și ecuațiile corespunzătoare, ceea ce corespunde definiției bazei.
Ați pregătit sistemul și ați găsit soluția de referință inițială – X0 = (0, 0, 0, 25, 20, 18). Acum prezentați coeficienții variabilelor și termenii liberi ai ecuațiilor (numerele din dreapta semnului „=") sub forma unui tabel pentru a optimiza calculele ulterioare (vezi figura).
Esența metodei simplex este de a aduce acest tabel într-o formă în care toate numerele din rândul L vor fi valori nenegative. Dacă se dovedește că acest lucru este imposibil, atunci sistemul nu are deloc o soluție optimă. Mai întâi, selectați cel mai mic element al acestei linii, care este -9. Numărul este în a treia coloană. Convertiți variabila x3 corespunzătoare într-o variabilă de bază. Pentru a face acest lucru, împărțiți linia cu 3, astfel încât celula să se termine cu 1.
Acum aveți nevoie de celule și să treceți la 0. Pentru a face acest lucru, scădeți din numerele corespunzătoare ale celui de-al treilea rând cu 3. Din elementele celui de-al doilea rând - elementele celui de-al treilea, înmulțite cu 2. Și, în cele din urmă, din elementele rândului L - înmulțite cu (-9). Ați obținut a doua soluție de referință: f(x) = L = 54 cu x1 = (0, 0, 6, 7, 8, 0).
