Metoda dual simplex. Exemplu de soluție detaliată. Metoda simplex pentru rezolvarea problemelor
Scopul serviciului. Calculator online folosit pentru rezolvarea problemelor de programare liniară P-metodaîn următoarele forme de înregistrare: forma de înregistrare de bază a metodei simplex, sub formă de tabel simplex, în metoda simplex modificată.
Instructiuni pentru rezolvarea problemelor metoda dual simplex. Selectați numărul de variabile și numărul de rânduri (numărul de constrângeri), faceți clic pe Următorul. Soluția rezultată este salvată într-un fișier Word (vezi exemplu de soluție folosind metoda dual simplex).
În același timp, restricții precum x i ≥ 0 nu iei in calcul.Următoarele sunt, de asemenea, utilizate cu acest calculator:
Metodă grafică de rezolvare a ZLP
Rezolvarea problemei transportului
Rezolvarea unui joc de matrice
Folosind serviciul online, puteți determina prețul unui joc matrice (limitele inferioare și superioare), puteți verifica prezența unui punct de șa, puteți găsi o soluție la o strategie mixtă folosind următoarele metode: minimax, metoda simplex, grafică (geometrică). ), metoda lui Brown.
Extremul unei funcții a două variabile
Probleme de programare dinamică
Distribuiți 5 loturi omogene de mărfuri între trei piețe astfel încât să obțineți venituri maxime din vânzarea acestora. Veniturile din vânzări pe fiecare piață G(X) depind de numărul de loturi vândute de produs X și sunt prezentate în tabel.
| Volumul produsului X (în loturi) | Venitul G(X) | ||
| 1 | 2 | 3 | |
| 0 | 0 | 0 | 0 |
| 1 | 28 | 30 | 32 |
| 2 | 41 | 42 | 45 |
| 3 | 50 | 55 | 48 |
| 4 | 62 | 64 | 60 |
| 5 | 76 | 76 | 72 |
În metoda P, planul optim se obține prin deplasarea de-a lungul pseudoplanurilor. Pseudoplan- un plan în care sunt îndeplinite condițiile de optimitate, iar printre valorile variabilelor de bază x i se numără numere negative. Algoritm pentru metoda dual simplex include următorii pași:
- Întocmirea unui pseudo-plan. Sistemul de constrângeri al problemei inițiale conduce la un sistem de inegalități cu sensul „≤”.
- Verificarea optimității planului. Dacă condiția de optimitate nu este satisfăcută în planul de referință rezultat, atunci problema este rezolvată folosind metoda simplex.
- Selectarea rândului și coloanei de început. Dintre valorile negative ale variabilelor de bază, sunt selectate cele mai mari în valoare absolută. Linia corespunzătoare acestei valori este cea din frunte.
- Calculul unui nou plan de referință. Noul plan se obține prin recalcularea tabelului simplex folosind metoda Jordan-Gauss. Apoi, treceți la etapa 2.
Exemplu. Întreprinderea trebuie să producă unități A1, unități A2 și unități A3 conform planului de producție. Fiecare tip de produs poate fi produs pe două mașini.
Cum să distribuiți munca mașinilor astfel încât timpul total petrecut pentru executarea planului să fie minim? Sunt date matricea costurilor și resursele de timp ale fiecărei mașini. Notați modelul operației studiate într-o formă care să permită utilizarea metodei P.
Se știe că conținutul de n nutrienți A, B și C din dietă ar trebui să fie de cel puțin m1, m2, respectiv m3 unități. Trei tipuri de alimente conțin acești nutrienți. Conținutul de unități nutritive într-un kilogram din fiecare tip de produs este prezentat în tabel. Stabiliți o dietă zilnică care să ofere cantitatea necesară de nutrienți la un cost minim.
Sarcină: Rezolvați problema utilizând algoritmul metodei dual simplex.
Să reducem sistemul de restricții la sistemul de inegalități de sens ≤ prin înmulțirea dreptelor corespunzătoare cu (-1).
Să determinăm valoarea minimă a funcției obiectiv F(X) = 4x 1 + 2x 2 + x 3 în următoarele condiții de constrângere.
- x 1 - x 2 ≤-10
2x 1 + x 2 - x 3 ≤8
Pentru a construi primul plan de referință, reducem sistemul de inegalități la un sistem de ecuații prin introducerea de variabile suplimentare (tranziție la forma canonică).
În prima inegalitate de sens (≤), introducem variabila de bază x 4 . În a doua inegalitate de sens (≤), introducem variabila de bază x 5 .
-1x 1 -1x 2 + 0x 3 + 1x 4 + 0x 5 = -10
2x 1 + 1x 2 -1x 3 + 0x 4 + 1x 5 = 8
Matricea de coeficienți A = a(ij) a acestui sistem de ecuații are forma:
| A= |
|
x 4, x 5,
Presupunând că variabilele libere sunt egale cu zero, obținem primul proiect de referință:
X1 = (0,0,0,-10,8)
| Bază | B | x 1 | x 2 | x 3 | x 4 | x 5 |
| x 4 | -10 | -1 | -1 | 0 | 1 | 0 |
| x 5 | 8 | 2 | 1 | -1 | 0 | 1 |
| F(X0) | 0 | -4 | -2 | -1 | 0 | 0 |
Iterația #1
Planul 0 dintr-un tabel simplex este un pseudo-plan, așa că determinăm rândul și coloana de început.
Linia principală va fi prima linie, iar variabila x 4 ar trebui derivată din bază.
3. Definirea unei noi variabile de bază. Valoarea minimă a lui θ corespunde coloanei a 2-a, adică. variabila x 2 trebuie introdusă în bază.
| Bază | B | x 1 | x 2 | x 3 | x 4 | x 5 |
| x 4 | -10 | -1 | -1 | 0 | 1 | 0 |
| x 5 | 8 | 2 | 1 | -1 | 0 | 1 |
| F(X0) | 0 | -4 | -2 | -1 | 0 | 0 |
| θ | 0 | -4: (-1) = 4 | -2: (-1) = 2 | - | - | - |
4. Recalcularea tabelului simplex. Efectuăm transformări ale tabelului simplex folosind metoda Jordano-Gauss.
| Bază | B | x 1 | x 2 | x 3 | x 4 | x 5 |
| x 2 | 10 | 1 | 1 | 0 | -1 | 0 |
| x 5 | -2 | 1 | 0 | -1 | 1 | 1 |
| F(X0) | 20 | -2 | 0 | -1 | -2 | 0 |
Să prezentăm calculul fiecărui element sub forma unui tabel:
| B | x 1 | x 2 | x 3 | x 4 | x 5 |
| -10: -1 | -1: -1 | -1: -1 | 0: -1 | 1: -1 | 0: -1 |
| 8-(-10 1):-1 | 2-(-1 1):-1 | 1-(-1 1):-1 | -1-(0 1):-1 | 0-(1 1):-1 | 1-(0 1):-1 |
| 0-(-10 -2):-1 | -4-(-1 -2):-1 | -2-(-1 -2):-1 | -1-(0 -2):-1 | 0-(1 -2):-1 | 0-(0 -2):-1 |
Iterația #2
1. Verificarea criteriului de optimitate.
Planul 1 dintr-un tabel simplex este un pseudo-plan, așa că determinăm rândul și coloana de început.
2. Definirea unei noi variabile libere.
Dintre valorile negative ale variabilelor de bază, o selectăm pe cea mai mare în valoare absolută.
A doua linie va fi lider, iar variabila x 5 ar trebui derivată din bază.
3. Definirea unei noi variabile de bază. Valoarea minimă a lui θ corespunde celei de-a treia coloane, adică. variabila x 3 trebuie introdusă în bază.
La intersecția rândului principal și coloanei există un element de rezoluție (RE) egal cu (-1).
| Bază | B | x 1 | x 2 | x 3 | x 4 | x 5 |
| x 2 | 10 | 1 | 1 | 0 | -1 | 0 |
| x 5 | -2 | 1 | 0 | -1 | 1 | 1 |
| F(X0) | 20 | -2 | 0 | -1 | -2 | 0 |
| θ | 0 | - | - | -1: (-1) = 1 | - | - |
4. Recalcularea tabelului simplex. Efectuăm transformări.
| Bază | B | x 1 | x 2 | x 3 | x 4 | x 5 |
| x 2 | 10 | 1 | 1 | 0 | -1 | 0 |
| x 3 | 2 | -1 | 0 | 1 | -1 | -1 |
| F(X1) | 22 | -3 | 0 | 0 | -3 | -1 |
| B | x 1 | x 2 | x 3 | x 4 | x 5 |
| 10-(-2 0):-1 | 1-(1 0):-1 | 1-(0 0):-1 | 0-(-1 0):-1 | -1-(1 0):-1 | 0-(1 0):-1 |
| -2: -1 | 1: -1 | 0: -1 | -1: -1 | 1: -1 | 1: -1 |
| 20-(-2 -1):-1 | -2-(1 -1):-1 | 0-(0 -1):-1 | -1-(-1 -1):-1 | -2-(1 -1):-1 | 0-(1 -1):-1 |
În coloana de bază, toate elementele sunt pozitive. Să trecem la algoritmul principal al metodei simplex.
Iterația #3
1. Verificarea criteriului de optimitate.
Nu există valori pozitive printre valorile șirului de index. Prin urmare, acest tabel determină planul optim pentru problemă.
| Bază | B | x 1 | x 2 | x 3 | x 4 | x 5 |
| x 2 | 10 | 1 | 1 | 0 | -1 | 0 |
| x 3 | 2 | -1 | 0 | 1 | -1 | -1 |
| F(X1) | 22 | -3 | 0 | 0 | -3 | -1 |
Planul optim poate fi scris astfel: x 1 = 0, x 2 = 10, x 3 = 2
F(X) = 2 10 + 1 2 = 22
Scris sub forma problemei principale, pentru care dintre vectori , compus din coeficienți pentru necunoscute în sistemul de ecuații, există m singur. În același timp, metoda dual simplex poate fi utilizată atunci când se rezolvă o problemă de programare liniară, ai cărui termeni liberi ai sistemului de ecuații pot fi orice numere(la rezolvarea problemei folosind metoda simplex, s-a presupus că aceste numere sunt nenegative). Vom lua în considerare acum o astfel de problemă, presupunând anterior că vectorii sunt unitari, adică vom lua în considerare problema constând în determinarea valorii maxime a funcției.
(54)
in conditii
(55)
(56)
Unde
iar printre numere sunt și negative.
În acest caz, există o soluție la sistemul de ecuații liniare (55). Totuși, această soluție nu este un plan pentru problema (54) – (56), deoarece printre componentele sale există numere negative.
Din moment ce vectorii –
unitate, fiecare dintre vectori poate fi reprezentat ca o combinație liniară a acestor vectori, iar coeficienții de descompunere a vectorilor în vectori sunt numere
T Cum se poate găsi
Definiția 14.
Soluția sistemului de ecuații liniare (55), determinată de bază, se numește pseudoplan probleme (54) – (56), dacă există
Teorema 11.
Dacă într-un pseudo plan , definit bază,există cel puțin un număr negativ astfel încât toate , apoi sarcina(54) – (56) nu are planuri deloc.
Teorema 12.
Dacă în pseudoplanul definit de bază există numere negative astfel încât pentru oricare dintre ele există numere a ij<0, то можно перейти к новому псевдоплану , при котором значение целевой функции задачи (54) – (56) nu va scadea.
Teoremele formulate oferă baza pentru construirea unui algoritm pentru metoda dual simplex.
Deci, să continuăm să luăm în considerare problema (54) – (56). Să fie pseudoplanul acestei probleme. Pe baza datelor inițiale, se întocmește un tabel simplex (Tabelul 15), în care unele elemente ale coloanei vectoriale sunt numere negative. Dacă nu există astfel de numere, atunci planul optim pentru problema (54) – (56) este scris în tabelul simplex, deoarece, prin presupunere, totul . Prin urmare, pentru a determina planul optim al problemei, cu condiția ca acesta să existe, ar trebui să se facă o tranziție ordonată de la un tabel simplex la altul până când elementele negative sunt excluse din coloana vectorială. În acest caz, toate elementele trebuie să rămână nenegative în orice moment ( T+1)-a linie, adică pentru oricine
Astfel, după compilarea unui tabel simplex, ei verifică dacă există numere negative în coloana vectorială. Dacă nu există, atunci este găsit planul optim pentru problema inițială. Dacă există (ceea ce presupunem), atunci alegeți numărul negativ care este cel mai mare în valoare absolută. În cazul în care există mai multe astfel de numere, luați unul dintre ele: lăsați acest număr b l . Alegerea acestui număr determină , exclus din bază, adică în acest caz, vectorul este derivat din bază P l . Pentru a determina ce vector trebuie introdus în bază, găsim , unde
Fie ca această valoare minimă să fie luată atunci când vectorul este introdus în bază R r . Numărul este elementul de rezolvare. Tranziția la un nou tabel simplex se efectuează conform regulilor obișnuite ale metodei simplex. Procesul iterativ continuă până la coloana vectorului R 0 nu vor mai fi numere negative. În acest caz, se găsește planul optim pentru problema inițială și, prin urmare, cea duală. Dacă la un pas se va dovedi că i-a linie a tabelului simplex (Tabelul 15) în coloana vector R 0 este un număr negativ b i , și nu există elemente negative printre elementele rămase ale acestei linii, atunci problema inițială nu are soluție.
Astfel, găsirea unei soluții la problema (54) – (56) folosind metoda dual simplex include următorii pași:
1. Găsiți un pseudoplan pentru problemă.
2. Verificați acest pseudo-plan pentru optimitate. Dacă pseudoplanul este optim, atunci a fost găsită o soluție la problemă. În caz contrar, fie stabilesc imposibilitatea de rezolvare a problemei, fie trec la un nou pseudo-plan.
3. Selectați linia de rezolvare determinând cel mai mare număr negativ din valoarea absolută a coloanei vectoriale R 0 și coloana de rezolvare prin găsirea celui mai mic raport al elementului cu valoare absolută ( m+1)–și linii la elementele negative corespunzătoare ale liniei de rezoluție.
4. Găsiți un nou pseudo-plan și repetați toate acțiunile începând cu etapa 2.
Tabelul 15
Exemplul 17.
Găsiți valoarea maximă a funcției în condiții
Soluţie.Să scriem problema de programare liniară originală sub forma problemei principale: găsi functionare maxima in conditii
Să înmulțim a doua și a treia ecuație a sistemului de constrângeri a ultimei probleme cu –1 și trecem la următoarea problemă: găsiți maximul funcției
(57)
in conditii
(58)
(59)
Să creăm o problemă dublă pentru ultima problemă. Aceasta este o problemă a cărei rezolvare necesită găsirea valorii minime a funcției
(60)
in conditii
(61)
(62)
După ce au ales vectorii și ca bază, vom compila un tabel simplex (Tabelul 16) pentru problema inițială (57) – (59).
Tabelul 16
|
i |
Bază |
C b |
R 0 |
|||||
|
P 1 |
P 2 |
P 3 |
p 4 |
p 5 |
||||
|
p 3 P 4 p 5 |
–4 –6 |
–1 –1 |
–2 |
Din acest tabel vedem că planul problemei duale (57) – (59) este . Cu acest plan T este același ca în coloana vectorului R 0 tabelul 16 sunt două numere negative (–4 și –6), iar în a 4-a linie nu există numere negative, apoi în conformitate cu algoritmul metodei dual simplex trecem la un nou tabel simplex. (În acest caz, acest lucru se poate face, deoarece în rândurile de vectori R 4 Și R 5 sunt numere negative. Dacă ar lipsi, problema ar fi de nerezolvat. Vectorul exclus din bază este determinat de cel mai mare număr negativ în valoare absolută din coloana vectorului R 0 . În acest caz, numărul este –6. Prin urmare, excludem vectorul din bază R 5 . Pentru a determina ce vector trebuie introdus în bază, găsim unde avem
Aceasta înseamnă că introducem vectorul în bază P 2 . Să trecem la noul ex-table simplu (Tabelul 17).
Tabelul 17
|
i |
Bază |
C b |
R 0 |
|||||
|
P 1 |
P 2 |
P 3 |
p 4 |
p 5 |
||||
|
p 3 P 4 p 2 |
–7 |
–3/2 |
–1/2 |
Din acest tabel este clar că s-a obținut un nou plan pentru problema duală. În acest plan, valoarea formei sale liniare este. Astfel, folosind algoritmul metodei dual simplex, se face o tranziție ordonată dintr-un plan al. dublă problemă la alta.
Deoarece în coloana vectorului R 0 din tabelul 17 este un număr negativ –7, apoi luați în considerare elementele celui de-al doilea rând. Printre aceste numere există un negativ –3/2. Dacă un astfel de număr ar lipsi, atunci problema inițială ar fi de nerezolvat. În acest caz, trecem la un nou tabel simplex (Tabelul 18).
Tabelul 18
|
i |
Bază |
C b |
R 0 |
|||||
|
P 1 |
P 2 |
P 3 |
p 4 |
p 5 |
||||
|
p 3 P 1 p 2 |
14/3 32/3 |
–2/3 |
–1/3 –1/3 |
După cum se poate observa din Tabelul 18, s-au găsit planuri optime pentru problemele originale și duale. Sunt 
Și . Cu aceste planuri, valorile formelor liniare ale problemelor originale și duale sunt egale: 
Exemplul 18.
Găsiți valoarea maximă a unei funcții 
in conditii
Soluţie.Înmulțind prima și a treia ecuație a sistemului de constrângeri ale problemei cu –1, ca rezultat ajungem la problema găsirii valorii maxime a funcției în condițiile
Luând vectori ca bază R 3 ,R 4 și R 5, alcătuim un tabel simplex (Tabelul 19).
Tabelul 19
|
i |
Bază |
C b |
R 0 |
|||||
|
P 1 |
P 2 |
P 3 |
p 4 |
p 5 |
||||
|
p 3 P 4 p 5 |
–12 –18 |
–3 |
–1 |
Nu există numere negative în al 4-lea rând al tabelului 19. Prin urmare, dacă în coloana vector R 0 nu existau numere negative, atunci planul optim ar fi scris în tabelul 19. Deoarece există numere negative în coloana indicată și aceleași numere sunt conținute în rândurile corespunzătoare, trecem la un nou tabel simplex (Tabelul 20). Pentru a face acest lucru, excludem vectorul din bază R 5 și introduceți vectorul în bază R 1 . Ca rezultat, obținem un pseudo-plan X=(6;0;-24;4)
Tabelul 20
|
i |
Bază |
C b |
R 0 |
|||||
|
P 1 |
P 2 |
P 3 |
p 4 |
p 5 |
||||
|
p 3 P 4 p 1 |
–24 |
–2/3 |
–1/3 |
Deoarece în linia vectorială R 3 nu există numere negative, atunci problema inițială nu are soluție.
Scurtă teorie
Au fost propuse multe metode diferite pentru a rezolva probleme de programare liniară. Cu toate acestea, metoda simplex s-a dovedit a fi cea mai eficientă și universală dintre ele. Trebuie remarcat faptul că la rezolvarea unor probleme, alte metode pot fi mai eficiente. De exemplu, pentru un ZLP cu două variabile, metoda optimă este , iar pentru rezolvarea acesteia se folosește metoda potențialului. Metoda simplex este de bază și aplicabilă oricărui PPL în formă canonică.
În legătură cu teorema principală a programării liniare, apare în mod firesc gândul despre următoarea modalitate de a rezolva LLP cu orice număr de variabile. Găsiți într-un fel toate punctele extreme ale poliedrului de planuri (nu sunt mai multe decât ) și comparați valorile funcției obiective la ele. O astfel de soluție, chiar și cu un număr relativ mic de variabile și restricții, este practic imposibilă, deoarece procesul de găsire a punctelor extreme este comparabil ca dificultate cu rezolvarea problemei inițiale și, în plus, numărul de puncte extreme ale poliedrului de planuri poate fie foarte mare. În legătură cu aceste dificultăți, s-a pus problema enumerarii raționale a punctelor extreme.
Esența metodei simplex este următoarea. Dacă sunt cunoscute un punct extrem și valoarea funcției obiectiv la acesta, atunci toate punctele extreme la care funcția obiectiv ia cea mai proastă valoare sunt evident că nu sunt necesare. Prin urmare, dorința naturală este de a găsi o modalitate de a trece de la un punct extrem dat la unul mai bun adiacent de-a lungul marginii, de la acesta la unul și mai bun (nu mai rău) etc. Pentru a face acest lucru, trebuie să aveți un semn că nu există puncte extreme mai bune decât un punct extrem dat. Aceasta este ideea generală a celei mai utilizate metode simplex în prezent (metoda de îmbunătățire secvențială a planului) pentru rezolvarea ZLP. Deci, în termeni algebrici, metoda simplex presupune:
- capacitatea de a găsi un plan de referință inițial;
- prezența unui semn de optimitate a planului de referință;
- capacitatea de a trece la un plan de referință care nu este cel mai rău.
Exemplu de rezolvare a problemei
Sarcina
Pentru a vinde trei grupe de bunuri, o întreprindere comercială are trei tipuri de resurse materiale și monetare limitate în valoare de , , , unități. În același timp, pentru vânzarea unui grup de mărfuri pentru 1 mie de ruble. cifra de afaceri de mărfuri consumă resursa de primul tip în numărul de unități, resursa de al doilea tip în numărul de unități, resursa de al treilea tip în numărul de unități. Pentru vânzarea a 2 și 3 grupuri de mărfuri pentru 1 mie de ruble. cifra de afaceri a mărfurilor este cheltuită în funcție de resursa de primul tip în valoare de , unități, resurse de al doilea tip în valoare de , unități, resurse de al treilea tip în valoare de , unități. Profitați din vânzarea a trei grupuri de mărfuri pentru 1 mie de ruble. cifra de afaceri este, respectiv, de mii de ruble.
- Determinați volumul planificat și structura cifrei de afaceri comerciale astfel încât profitul întreprinderii comerciale să fie maximizat.
- Pentru problema directă a planificării cifrei de afaceri, rezolvată prin metoda simplex, creați o problemă de programare liniară duală.
- Stabiliți perechi conjugate de variabile ale problemelor directe și duale.
- După perechi conjugate de variabile, din rezolvarea problemei directe, se obține o soluție a problemei duale, în care se estimează resursele cheltuite pentru vânzarea mărfurilor.
Dacă admiterea ta la sesiune depinde de rezolvarea unui bloc de probleme și nu ai nici timpul și nici dorința de a te așeza la calcule, folosește capacitățile site-ului. Comandarea sarcinilor durează doar câteva minute. Puteți citi în detaliu (cum depuneți o cerere, prețuri, termeni, modalități de plată) pe pagina Cumpărați soluții la problemele de programare liniară...
Rezolvarea problemei
Construirea modelului
Să notăm cifra de afaceri din primul, al doilea și, respectiv, al treilea tip de mărfuri.
Apoi funcția obiectiv care exprimă profitul primit:
Limitări ale resurselor materiale și monetare:
În plus, conform sensului sarcinii
Obținem următoarea problemă de programare liniară:
Reducerea la forma canonică a ZLP
Să aducem problema în formă canonică. Pentru a transforma inegalitățile în egalități, introducem variabile suplimentare. Variabilele sunt incluse în restricții cu un coeficient de 1. Introducem toate variabilele suplimentare în funcția obiectiv cu un coeficient egal cu zero.
Constrângerea are o formă preferabilă dacă, cu partea dreaptă nenegativă, partea stângă are o variabilă care intră cu un coeficient egal cu unu, iar restul constrângerilor de egalitate au un coeficient egal cu zero. În cazul nostru, restricțiile 1, 2, 3 au o formă preferată cu variabilele de bază corespunzătoare.
Rezolvare folosind metoda simplex
Completam tabelul simplex al celei de-a 0-a iterații.
| BP | Simplex relaţie |
8 | 6 | 4 | 0 | 0 | 0 | 0 | 520 | 16 | 18 | 9 | 1 | 0 | 0 | 65/2 | 0 | 140 | 7 | 7 | 2 | 0 | 1 | 0 | 20 | 0 | 810 | 9 | 2 | 1 | 0 | 0 | 1 | 90 | 0 | -8 | -6 | -4 | 0 | 0 | 0 |
Întrucât rezolvăm problema la maximum, prezența numerelor negative în linia index atunci când rezolvăm problema la maximum indică faptul că nu am obținut soluția optimă și că este necesar să trecem de la tabelul celei de-a 0-a iterații. la următorul.
Trecem la următoarea iterație după cum urmează:
Coloana principală corespunde .
Rândul cheie este determinat de raportul minim dintre termenii liberi și membrii coloanei principale (relații simple):
La intersecția coloanei de cheie și a rândului de chei găsim elementul de activare, adică 7.
Acum începem să compilam prima iterație. În loc de un vector unitar, introducem vectorul .
În noul tabel, în locul elementului de activare scriem 1, toate celelalte elemente ale coloanei cheie sunt zerouri. Elementele șirului cheie sunt împărțite în elementul de activare. Toate celelalte elemente ale tabelului sunt calculate folosind regula dreptunghiului.
Obținem tabelul primei iterații:
| BP | Simplex relaţie |
8 | 6 | 4 | 0 | 0 | 0 | 0 | 200 | 0 | 2 | 31/7 | 1 | -16/7 | 0 | 1400/31 | 8 | 20 | 1 | 1 | 2/7 | 0 | 1/7 | 0 | 70 | 0 | 630 | 0 | -7 | -11/7 | 0 | -9/7 | 1 | - | 160 | 0 | 2 | -12/7 | 0 | 8/7 | 0 |
Coloana cheie pentru prima iterație corespunde .
Găsim linia cheie, pentru aceasta definim:
La intersecția coloanei de chei și a rândului de chei găsim elementul de activare, i.e. 31/7.
Vectorul este derivat de la bază și vectorul este introdus.
Obținem tabelul celei de-a doua iterații:
| BP | Simplex relaţie |
8 | 6 | 4 | 0 | 0 | 0 | 4 | 1400/31 | 0 | 14/31 | 1 | 7/31 | -16/31 | 0 | 8 | 220/31 | 1 | 27/31 | 0 | -2/31 | 9/31 | 0 | 0 | 21730/31 | 0 | -195/31 | 0 | 11/31 | -65/31 | 1 | 7360/31 | 0 | 86/31 | 0 | 12/31 | 8/31 | 0 |
În rândul index, toți termenii sunt nenegativi, deci se obține următoarea soluție la problema de programare liniară (o scriem din coloana de termeni liberi):
Astfel, este necesar să vindeți 7,1 mii de ruble. mărfuri de primul tip și 45,2 mii de ruble. bunuri de al 3-lea tip. Nu este profitabil să vinzi un produs de al 2-lea tip. În acest caz, profitul va fi maxim și se va ridica la 237,4 mii de ruble. Dacă planul optim este implementat, resursa rămasă de tipul 3 va fi de 701 unități.
Problema cu dublu LP
Să scriem un model al problemei duale.
Pentru a construi o problemă dublă, trebuie să utilizați următoarele reguli:
1) dacă problema directă se rezolvă la maximum, atunci problema duală se rezolvă la minimum și invers;
2) în problema maximului, constrângerile de inegalitate au sensul ≤, iar în problema de minimizare au sensul ≥;
3) fiecărei constrângeri a problemei directe corespunde unei variabile a problemei duale și invers, fiecărei constrângeri a problemei duale corespunde unei variabile a problemei directe;
4) matricea sistemului de restricții a problemei duale se obține din matricea sistemului de restricții a problemei inițiale prin transpunere;
5) termenii liberi ai sistemului de constrângeri ai problemei directe sunt coeficienți ai variabilelor corespunzătoare funcției obiective a problemei duale și invers;
6) dacă variabilei problemei directe i se impune o condiție de non-negativitate, atunci constrângerea corespunzătoare problemei duale se scrie ca o constrângere de inegalitate, dacă nu, atunci ca o constrângere de egalitate;
7) dacă orice constrângere a problemei directe este scrisă ca egalitate, atunci condiția de non-negativitate nu este impusă variabilei corespunzătoare problemei duale.
Transpunem matricea problemei originale:
Să aducem problema în formă canonică. Să introducem variabile suplimentare. Introducem toate variabilele suplimentare în funcția obiectiv cu un coeficient egal cu zero. Adăugăm variabile suplimentare în partea stângă a restricțiilor care nu au o formă preferată și obținem egalități.
Rezolvarea problemei duble LP
Corespondența dintre variabilele problemei originale și ale problemei duale:
Pe baza tabelului simplex, a fost obținută următoarea soluție la problema de programare liniară duală (o scriem din linia de jos):
Astfel, resursa de primul tip este cea mai rară. Scorul său este maxim și egal cu . Resursa de al treilea tip este redundantă - valoarea sa duală este zero. Fiecare unitate suplimentară de mărfuri din a 2-a grupă vândută va reduce profitul optim cu
Este considerată o metodă grafică pentru rezolvarea unei probleme de programare liniară (LPP) cu două variabile. Folosind exemplul unei probleme, se oferă o descriere detaliată a construirii unui desen și găsirea unei soluții.
Rezolvarea problemei transportului
Problema transportului, modelul său matematic și metodele de rezolvare sunt analizate în detaliu - găsirea planului de referință prin metoda elementului minim și căutarea soluției optime prin metoda potențialului.
Luarea deciziilor în condiții de incertitudine
Rezolvarea unui joc de matrice statistică în condiții de incertitudine este considerată folosind criteriile Wald, Savage, Hurwitz, Laplace și Bayes. Folosind un exemplu de problemă, construcția unei matrice de plată și a unei matrice de risc este prezentată în detaliu.
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 pentru produsele 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. Ea 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 non-bazice 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
nedegenerate. 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 suport și, respectiv, probleme de programare liniară directă și 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 duală 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 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. De asemenea, este posibilă efectuarea în buclă, adică o succesiune nesfârșită de pași inactiv. Pentru a o preveni, au fost dezvoltați algoritmi speciali - anticicline. Cu toate acestea, în marea majoritate 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 2-a linie, scădeți a 3-a 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ă vindeți 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 condiției originale 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 coloana 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.
Deci, treceri succesive de la unul bază conjugată altuia îl efectuează până când obțin o soluție a problemei sau stabilesc insolubilitatea acesteia. Fiecare tranziție de la un pseudoplan la altul este o iterație (un pas).
Fiecare iterație conține două etape. În prima etapă, ei află dacă pseudo-planul este plan optim problemă directă, iar dacă nu, atunci dacă problema este rezolvabilă. Pentru a face acest lucru, este necesar să se calculeze și să se stabilească semnele acestora. A doua etapă constă în efectuarea unei transformări elementare - (o iterație) metoda excluderii complete Jordan-Gauss, conducând la un nou pseudo-plan cu o valoare mai mică a funcției obiectiv.
Descrierea algoritmului. Problema LP trebuie specificată în forma canonică (1.1), (1.2) sau redusă la ea. Căuta bază conjugată dubla problema si desemneaza-l 
. Să extindem A 0 în vectorii de bază A i1 ,.,A im în conformitate cu (1.9) și să găsim pseudoplanul 
sarcină directă.
Să explorăm semnele (x i0). Dacă apare cazul, atunci pseudoplanul inițial este plan optim sarcină directă. Dacă există componente negative (x i0), calculăm coeficienții descompuneri vectoriale A j prin vectori bază conjugată(х ij) în conformitate cu (1.8).
Dacă pentru unele r astfel încât x r0<0 , все то задача не разрешима (второй случай), и на этом процесс вычислений заканчивается.
Dacă apare al treilea caz (adică pentru fiecare r astfel încât x r0<0 , по крайней мере одна из компонент х rj <0 ), то переходим к второму этапу. С этой целью составляют таблицу k -й итерации (аналогичную tabel simplex), care constă din (m+2) rânduri și (n+1) coloană (Tabelul 6.1).
Coloana B x a tabelului, ca de obicei, conține vectorii (A i) ai bazei pseudoplanului xk, iar coloana A 0 - componentele de bază ale pseudoplanului (x i0 (k)). Linia indicelui (m+1) este umplută cu parametrii care sunt estimări ale vectorilor A j:
valoare - valoarea funcției obiectiv pentru un pseudoplan
Iterația k se finalizează prin completarea părții principale a tabelului (de la primul la (m+1) rândurile al doilea).
| C | C 1 | C 2 | . | Cj | . | Cn | ||
| B x | A 0 | A 1 | A 2 | . | A j | . | A n | |
| C 1 | X 1 | X 10 | X 11 | X 12 | . | X 1j | . | X 1n |
| C 2 | X 2 | X 20 | X 21 | X 22 | . | X2j | . | X2n |
| . | . | . | . | . | . | . | . | . |
| C i | X i | Xi0 | Xi1 | Xi2 | . | X ij | . | Xin |
| . | . | . | . | . | . | . | . | . |
| Cm | X m | X m0 | X m1 | X m2 | . | X mj | . | X mn |
| . | . | |||||||
| . | . |
În prima etapă (k + 1) - iar iterațiile află dacă apare primul, al doilea sau al treilea caz.
În al treilea caz, trecem la a doua etapă. În primul rând, se determină vectorul A r, care trebuie derivat din bază. Indicele său r este determinat din condiție
Doar acele poziții pentru care x rj sunt completate în linie<0 . Вектор А l , который должен быть введен в базис, находят из условия
După ce s-au determinat rândul de ghidare r și coloana l, elementele părții principale a tabelului a (k+1)-a iterație sunt calculate folosind relații de recurență
 |
(1.15) |
Unde x ri este elementul de ghidare a transformării.
Schema de calcul a algoritmului metoda dual simplex similar cu schema de calcul a metodei simplex. Formele tabelelor sunt similare.
Diferența dintre metode este că prin metoda simplex se face o tranziție secvențială de la o soluție de bază fezabilă (plan de referință) a problemei la alta și cu metoda simplă duală- trecerea de la un pseudoplan la altul.
Diferența formală dintre schemele de calcul ale acestor metode se manifestă numai în regulile de tranziție de la o bază la alta, precum și în semnele de optimitate și insolubilitate ale problemei. În metoda simplex, se determină mai întâi vectorul introdus în bază, apoi se determină vectorul exclus din bază, iar în metoda dual simplex această ordine este inversă.
Să notăm câteva proprietăți importante metoda dual simplex.
Spre deosebire de direct
