Agenția Federală pentru Educație

Stat instituție educațională studii profesionale superioare

Universitatea Tehnică de Stat Perm

filiala Lysvensky

Departamentul de Economie

Lucrări de curs

la disciplina „Analiză de sisteme și cercetare operațională”

pe tema: „Metoda simplex în formă de prezentare”

Completat de un elev din grupa VIVT-06-1:

Startseva N. S.

Verificat de profesor:

Mukhametyanov I.T.

Lysva 2010

Introducere. 3

Programare matematică. 5

Metoda grafică. 6

Metoda simplex tabelar. 6

Metodă baza artificiala. 7

Metoda simplex modificată. 7

Dual simplex - metoda. 7

Vedere generală a problemei programare liniară. 9

Rezolvarea unei probleme de programare liniară folosind metoda simplex. unsprezece

Proceduri de calcul ale metodei simplex. unsprezece

Teorema 1: 13

Teorema 2: 14

Teorema 3: 15

Teorema 4: 15

Teorema 5: 15

Trecerea la un nou plan de referință. 15

Sarcină dublă. 17

Teorema 1 (prima teoremă a dualității) 18

Teorema 2 (a doua teoremă a dualității) 18

Concluzie. 20

Soluția optimă a problemei de programare liniară se numără printre soluțiile de referință. Ideea metodei simplex este că, după o anumită regulă, soluțiile de referință sunt sortate până când se găsește cea optimă printre ele Prin sortarea soluțiilor de referință, în esență, sortăm diverse variabile de bază , la pasul următor, o variabilă este transferată din rândul celor de bază, iar în schimb o anumită variabilă din numărul celor libere în numărul celor de bază.

7x 1 +5x 2 →max

x 3 =19-2x 1 -3x 2 (0;0;19;13;15;18)

x 4 =13-2x 1 -x 2 initial plan de referință

x 6 =18-3x 1 F(x 1 , x 2)=7*0+5*0=0

x i ≥0, (i=1,…n)

La nivel intuitiv, este clar că va fi firesc să crești x 1, deoarece coeficientul pentru acesta este mai mare decât pentru x 2. Lăsând x 2 =0, putem crește până când x 3 , x 4 , x 5 , x 6 rămân nenegative.

x 1 =min(19/2;13/2;∞;18/3)=6

Aceasta înseamnă că atunci când x 1 =6, x 6 =0, adică x 1 intră în numărul celor de bază, iar x 6 intră în numărul celor libere.

x 3 =19-2(6-1/3 x 6)-3 x 2 =19-12+2/3 x 6 -3 x 2 =7+2/3 x 6 -3 x 2

x 4 =13-2(6-1/3 x 6)- x 2 =1+2/3 x 6 - x 2

F(x 2 ; x 6) =42-7/3 x 6 +5 x 2

Cu un plan de referință dat (6;0;7;1;15;0) x 2, transferați de la variabilele libere la variabilele de bază:

x 2 =min(∞;7/3;1/11;15/3)=1

Exprimați x 2 prin x 4

x 2 =1+2/3 x 6 - x 4

Exprimăm variabilele necunoscute și funcția obiectiv în termeni de variabile libere:

x 3 =7+2/3 x 6 -3(1+2/3x 6 –x 4)= 7+2/3 x 6 -3-2x 6 +3x 4 =4-4/3x 6 +3 x 4

x 5 = 12-2x 6 +3x 4 -

F=42-7/3 x 6 +5(1+2/3x 2 - x 4) =47-7/3x 6 +10/3x 6 -5x 4 =47+x 6 -5x 4

x 6 este pozitiv, prin urmare poate fi crescut

x 6 =min(18;∞;3;6)=1

x 4 =4/3-4/9 x 6 - 1/3x 3

F=47+x 6 -5(4/3-4/9-1/3x 3)

În funcția obiectiv, toți coeficienții variabilelor sunt negativi, valoarea funcției nu poate fi mărită, transformăm în mod similar variabilele rămase, găsim planul de referință, din care determinăm x 1, x 2;

1. Intersecția mulțimilor închise, un set de restricții netriviale.

2. Mulțimea soluțiilor unui sistem de inegalități și ecuații liniare nestrictive este închisă.

αX=(αx 1 ,x 2 ,…, αx n)

X+Y=(x 1 +y 1, x 2 +y 2,... x n +y n)

Coordonatele liniare X 1 ,X 2 ,…X n se numesc punct P=λ 1 x 1 + λ 2 x 2 +…+ λ k x k

Mulțimea P=(λ 1 x 1 + λ 2 x 2 +…+ λ k x k ) 0≤ h i ≤1 pentru i= 1,…k n åR i =1, 1≤ i ≤k combinație liniară convexă de puncte x 1 ,x 2 ,…x n . Dacă k=2, atunci această mulțime se numește segment. X 1,X 2 – capete ale segmentului. Un punct de colț al unei mulțimi închise este un punct care nu este o combinație liniară netrivială de puncte din mulțime (punct de colț).

Non-trivialitate înseamnă că cel puțin unul dintre λ este diferit de 0 sau 1.

Orice soluție de referință la o problemă de programare liniară este un punct de colț al regiunii soluțiilor fezabile.

Dacă o problemă de programare liniară are singura decizie, apoi se află printre punctele de colț ale ODR. Și dacă există mai multe soluții, atunci printre soluții există mai multe unghiulare, astfel încât mulțimea tuturor soluțiilor să fie combinația lor liniară convexă.

Metoda simplex constă în găsirea mai întâi a unei anumite soluții de referință a problemei (planul de referință inițial), apoi, trecerea intenționată de la un plan de referință la altul, căutarea planului optim. Dacă sunt mai multe dintre ele, atunci se găsesc toate cele de colț, iar mulțimea soluțiilor este reprezentată ca combinație liniară a acestora.

Trecerea la un nou plan de referință

F1 =F(x 1); F 2 =F(x 2) F 2 -F 1 =-υ k Δ k =F 2 se poate dovedi, unde υ k este minimul considerat mai sus, care se determină prin introducerea k-a variabilă în bază, și Δ k =åс j x j ( 1) -С k, unde n ≤ j ≤1, X 1 =(x 1 (1) ;x 2 (1) ;…x n (1)) este o estimare a k-a variabilă , deci dacă problema maximă este rezolvată, atunci valoarea ΔF 2 trebuie să fie pozitivă, Δk trebuie să fie negativă. La rezolvarea problemelor minime, ΔF 2 este negativ, Δ k este pozitiv. Aceste valori sunt calculate și dacă între ΔF 2 toate valorile nu sunt pozitive, atunci când se rezolvă probleme la minim, este invers. Dacă la rezolvarea unui maxim există mai multe pozitive între ΔF 2, atunci introducem în bază vectorul la care această valoare atinge un maxim, iar dacă problema se rezolvă pentru un minim iar între ΔF 2 există mai multe negative. cele, atunci vectorul cu cea mai mică valoare ΔF 2 este inclus în bază, adică cu cea mai mare valoare absolută. Când aceste condiții sunt îndeplinite, se garantează cea mai mare modificare posibilă a valorii funcției.

Soluția problemei va fi unică dacă pentru orice vector x k neincluși în bază, se estimează Δ k ≠0, dacă cel puțin unul dintre aceștia Δ k = 0, atunci soluția nu este unică, pentru a găsi o altă soluție trecem la un alt plan de referință, inclusiv în baza x k, unde Δ k =0. Enumerarea tuturor acestor soluții de asistență le compun combinație liniară, care va fi soluția problemei.

Dacă pentru orice Δ k coeficienții pentru variabila x k ≤ 0 contrazic condiția de optimitate, atunci sistemul de restricții nu este limitat, adică nu există un plan optim.

Problemă dublă

O problemă duală (DP) este o problemă de programare liniară auxiliară formulată folosind anumite reguli direct din condițiile problemei directe. Interesul de a determina soluția optimă a unei probleme directe prin rezolvarea problemei sale duale se datorează faptului că calculele la rezolvarea unei DP se pot dovedi a fi mai puțin complexe decât la rezolvarea unei probleme directe (DP). Complexitatea calculelor când decizia PPP depinde mai mult de numărul de constrângeri decât de numărul de variabile. Pentru a merge la telecomanda, este necesar ca cunostintele tehnice sa fie scrise in standard formă canonică. La prezentarea PP-ului în formă standard, variabilele x j includ și variabile redundante și reziduale.

Problema dubla are:

1. m variabile corespunzătoare numărului de constrângeri ale problemei directe;

2. n restricţii corespunzătoare numărului de variabile ale problemei directe.

Problema duală se obține prin transformarea structurală simetrică a condițiilor problemei directe după următoarele reguli:

· Fiecare constrângere b i PD corespunde unei variabile y i PD;

· Fiecărei variabile x j PD îi corespunde o constrângere C j PD;

· Coeficienții pentru x j din constrângerile PD devin coeficienții din stânga constrângerii PD corespunzătoare;

· Coeficienții C j pentru x j în funcția țintă a PD devin constanți în partea dreaptă a constrângerii PD;

· Constantele de constrângere b i PD devin coeficienți ai funcției țintă PD.

Luați în considerare următoarele două probleme:

F = С 1 x 1 +С 2 x 2 +... +С n x n →max

(5)

a 11 x 1 + a 22 x 2 + ... + a 1m x n ≤ b 1

a 21 x 1 + a 22 x 2 + ... + a 2m x n ≤b 2

a m1 x 1 + a m2 x 2 + ... + a mn x n ≤b m

x j ≥0 j=1,…,n

Z = b 1 x 1 +b 2 x 2 +... +b n x n →min

(6)

a 11 y 1 + a 21 y 2 + ... + a m1 y 1 ≤ C 1

a 12 y 1 + a 22 y 2 + ... + a m 2 y 2 ≤C 2

. . . . . . . . . . . . . . . . . . . . . . .

a 1 n y n + a 2 m y n + ... + a nm y n ≤C n

Acest curs a pus bazele metode matematice rezolvarea problemelor de programare liniară. Prin urmare, s-a acordat mai multă atenție următoarelor secțiuni:

1. Fundamentele metodelor matematice și aplicarea acestora;

2. Rezolvarea problemelor folosind metoda simplex.

Există multe metode de rezolvare a problemelor de programare liniară. Să luăm în considerare una dintre ele, metoda simplex îmbunătățită (modificată).

Mai întâi, să vă spunem care este metoda simplex. Cuvântul SIMPLEX în sensul său obișnuit înseamnă simplu, necompus, spre deosebire de COMPLEX.

Această metodă a primit mai multe diferite forme(modificări) și a fost dezvoltată în 1947 de G. Danzig.

Esența metodei simplex este că dacă numărul de necunoscute mai mult număr ecuații, atunci acest sistem nesigur cu nenumărate soluții. Pentru a rezolva sistemul, toate necunoscutele sunt împărțite în mod arbitrar în de bază și gratuite. Numărul de variabile de bază este determinat de numărul de ecuații liniar independente. Necunoscutele rămase sunt gratuite. Li se dau valori arbitrare și sunt substituite în sistem. Orice set de necunoscute libere i se poate da un număr infinit de valori arbitrare, care vor da un număr infinit de soluții. Dacă toate necunoscutele libere sunt setate la zero, atunci soluția va consta din valorile necunoscutelor de bază. Această soluție se numește de bază.

În teoria programării liniare, există o teoremă care afirmă că printre soluțiile de bază ale sistemului se pot găsi optime și, în unele cazuri, mai multe soluții optime, dar toate vor oferi un extremum al funcției obiectiv. Astfel, dacă găsiți un plan de bază și apoi îl îmbunătățiți, veți obține soluție optimă. Metoda simplex este construită pe acest principiu.

Una dintre modificările metodei simplex este metoda simplex îmbunătățită. În literatură, această metodă se regăsește și sub denumirea de metoda matricei inverse sau simplex modificat-metodă.

Când se rezolvă probleme de programare liniară în care n (numărul de variabile) este semnificativ mai mare decât m (numărul de constrângeri), metoda simplex îmbunătățită necesită mult mai puține operații de calcul și memorie de calculator în comparație cu altele.

Metoda simplex îmbunătățită implementează aceeași idee de bază ca metoda simplex convențională, dar aici la fiecare iterație nu se recalculează întreaga matrice A -1, inversul matricei de constrângeri A, ci doar acea parte care se referă la baza curentă A X.

Să luăm în considerare pas cu pas pașii rezolvării unei probleme de programare liniară folosind metoda simplex îmbunătățită:

• 1. La începutul primului ciclu știm matrice inversă (matrice de identitate), solutie de baza x b = b.
• 2. Pentru fiecare variabilă nebază, formăm diferența caracteristică j folosind ecuația:

j = c j -- = c j -- P j , (2)

unde sunt variabilele duale, care pot fi găsite după cum urmează:

unde c x este vectorul de coeficienți ai funcției obiectiv pentru variabilele de bază.

3. Presupunând că se utilizează regula standard pentru selectarea coloanei de intrare, găsim:

• 4. Dacă s 0, procedura se oprește. Soluția de bază actuală este optimă.
• 5. Dacă s 0, calculați coloana transformată:

= (, ...,) . (2.4)

Dacă toate sunt 0, procedura se oprește: optimul este nelimitat.

7. În caz contrar, găsim variabila derivată din baza:

8. Construim o matrice mărită:

și transformă-l cu elementul conducător. Primele m coloane dau inversul matricei noii baze.

9. Transformați soluția de bază:

x b i x b i -- * , i r, (2.7)

și treceți la etapa 2.

Această opțiune este numită și metoda simplex modificată, deoarece reduce cantitatea de calcul la fiecare pas. Ideea este că la fiecare pas forma canonică a problemei pentru baza curentă poate fi obținută independent de alte astfel de forme direct din înregistrarea originală a problemei LP standard.

Pentru a face acest lucru aveți nevoie de:

• 1. Păstrați evidența originală a sarcinii pe toată durata operațiunii metodei acesta este prețul pe care trebuie să-l plătiți pentru o performanță mai mare;
• 2. Utilizați așa-numitele simplex - multiplicatori p - coeficienți pentru trecerea directă de la înregistrarea originală a problemei la forma sa actuală de bază canonică;
• 3. Folosiți baza inversată BO№ - o matrice de dimensiune m x m, care vă permite să calculați coloana principală aґs la fiecare pas și să actualizați simplexul - factorii p.

Metoda simplex îmbunătățită are avantaje semnificative față de forma standard. Acest lucru se aplică cerințelor de precizie, viteză și memorie. Cele mai multe dintre aceste avantaje sunt determinate de faptul că, de regulă, matricele problemelor liniare mari (adică cu n>m>100) sunt slab umplute și conțin un procent mic de elemente nenule.

O densitate de 5% sau mai puțin este comună. O formă îmbunătățită a metodei simplex este mai capabilă să profite de avantajele care decurg din acest fapt. În această formă, diferențele caracteristice și vectorul conducător sunt calculate direct din datele originale. Deoarece matricea originală este slab umplută, iar înmulțirea ar trebui efectuată numai atunci când ambii factori sunt diferit de zero, timpul de calcul este redus semnificativ.

În plus, utilizarea numai a datelor originale înseamnă că posibilitatea de a acumula erori de rotunjire este redusă. În schimb, tabelele simplex standard, chiar dacă inițial sunt puțin populate, sunt umplute rapid cu elemente diferite de zero printr-un proces iterativ. Astfel, timpul de calcul crește și, deoarece fiecare tabel este calculat față de cel precedent, acumularea de erori poate începe să joace un rol mai serios.

Trimiteți-vă munca bună în baza de cunoștințe este simplu. Utilizați formularul de mai jos

Buna treaba la site">

Studenții, studenții absolvenți, tinerii oameni de știință care folosesc baza de cunoștințe în studiile și munca lor vă vor fi foarte recunoscători.

Documente similare

Soluție geometrică sarcini standard programare liniară cu două variabile. Metoda universală solutii problema canonica. Ideea principală a metodei simplex, implementare folosind un exemplu. Implementarea tabelară a unei metode simplex simple.

rezumat, adăugat 15.06.2010


Tipuri de probleme de programare liniară și formularea problemelor. Esența optimizării ca ramură a matematicii și caracteristicile principalelor metode de rezolvare a problemelor. Conceptul metodei simplex, probleme aplicate reale. Algoritm și etape de rezolvare a problemei transportului.

lucrare de curs, adăugată 17.02.2010


Rezolvarea problemelor de programare liniară folosind metode grafice și simplex. Rezolvarea problemei dublă cu cea inițială. Determinarea planului optim de repartizare a consumatorilor către furnizorii de marfă omogenă, sub rezerva minimizării kilometrajului total al vehiculului.

test, adaugat 15.08.2012


Utilizarea metodei simplex pentru rezolvarea problemelor de programare liniară pentru a calcula volumul zilnic de producție. Verificarea optimității planului. Recalculare tabel simplex metoda Jordan-Gauss. Întocmirea unui model al unei probleme de transport.

test, adaugat 18.02.2014


Model economic si matematic pentru obtinerea profitului maxim, solutia acestuia metoda grafica. Algoritm pentru rezolvarea unei probleme de programare liniară folosind metoda simplex. Elaborarea unei probleme duble și a acesteia solutie grafica. Soluție matrice de plată.

test, adaugat 05.11.2014


Bazele modelare matematică proceselor economice. caracteristici generale metode grafice și simplex pentru rezolvarea problemelor de programare liniară directă și duală. Caracteristici ale formulării și metodologiei de rezolvare a problemei transportului.

lucrare de curs, adăugată 11.12.2010


Compilare model matematic sarcini. Calculul planului optim de transport cu costul minim folosind metoda potențială. Cea mai bună opțiune echipamente mobile speciale pt suport tehnic managementul producției.

test, adaugat 06.01.2014

METODA SIMPLEX MODIFICATĂ Metoda simplex nu este cea mai eficientă
procedură computerizată, întrucât calculează şi
stochează informații care nu sunt necesare pentru curent
iterație și nu poate fi folosit deloc pentru
luarea deciziilor în timpul iterațiilor ulterioare. Pentru
coeficienţii variabilelor non-principale din ecuaţie
(0), coeficienții principalelor variabile introduse
în alte ecuații și în partea dreaptă a ecuațiilor la
Fiecare iterație folosește doar cea relevantă
informație. Prin urmare, este nevoie de o procedură care
pot obține aceste informații în mod eficient, fără
calcule și stocare a tuturor celorlalți coeficienți
(aceasta este metoda simplex modificată).

Acesta calculează și stochează doar informații
necesar pentru acest moment, și date importante
transmite într-o formă mai compactă.
Folosește operații matrice, deci
este necesar să descriem problema folosind matrice.
Litere majuscule, evidențiate cu aldine
reprezintă matrici, majuscule,
cele cu caractere aldine reprezintă
vectori.
Cursivele sunt mărimi scalare, evidențiate zero
(0) indică vectorul zero (elementele sale sunt egale
zero, atât rânduri, cât și coloane), zero (0)
este număr obișnuit 0. Folosind
matrice forma standard a modelului liniar
programarea ia forma:

Maximizați Z = c x,
conform
A x ≤ b și x ≥ 0,
unde c este un vector rând
x, b și 0 vectori coloană

A - matrice
Pentru forma augmentată, vector coloană
variabile fictive:
Restrictii:
I = (m × m matrice de identitate)
0 = (n + m elemente ale vectorului zero)

Găsirea unei soluții de bază fezabile
Abordarea generală a metodei simplex este de a obține
succesiune de îmbunătățire a soluțiilor OA până la
până când se găsește cea optimă
soluţie. Una dintre caracteristicile cheie
metoda simplex modificată - cum
găsește o nouă soluție OD după ce a definit-o
principal (de bază) și non-bază (non-bază)
variabile. Având în vedere aceste variabile, rezultatul
soluție principală – soluție a m ecuații
În care n variabile nebaze din n + m
elemente
sunt setate egale cu zero.

Eliminarea acestor n variabile prin setarea lor la zero,
obţinem un sistem de ecuaţii m cu m variabile
(variabile principale (de bază):
unde este vectorul variabilelor de bază:
obţinut prin excluderea non-bazic (non-bazic)
variabile:

ȘI matricea de bază
Rezultatul obţinut prin excluderea coloanelor corespunzătoare
coeficienţii variabilelor nebazice din .
(În plus, elementele xB și coloanele B sunt diferite
Bine). Metoda simplex introduce doar de bază
variabile astfel încât B este nedegenerat, deci
matricea inversă B-1 va exista întotdeauna.
Pentru a rezolva B x B = b, ambele părți sunt înmulțite cu B-1:
B-1 B x B = B-1 b.

cB este un vector ale cărui elemente sunt coeficienți
funcții obiective (inclusiv zerouri pentru manechin
variabile) pentru elementele xB corespunzătoare.
Funcția obiectiv pentru această soluție de bază este:

Exemplu:
- Iterația 0
asa de
asa de

10.

- Iterația 1
asa de
asa de

11.

- Iterația 2
asa de
asa de

12. Forma matriceală pentru setul curent de ecuații

Forma matriceală pentru un set de ecuații,
care apar în tabelul simplex pentru orice iterație
metoda originală simplex. Pentru sistemul original
ecuații, forma matricei este:
Operații algebrice efectuate folosind metoda simplex (înmulțiți ecuația cu o constantă și adăugați
produsul unei ecuații cu alta) sunt exprimate în
forma matriceală, după înmulțirea ambelor părți
sistemul original de ecuații în corespunzătoare
matrici

13.

14.

Această matrice va avea aceleași elemente ca și matricea de identitate
matrice, cu excepția faptului că fiecare produs
pentru o anumită operație algebrică va fi nevoie
spațiul necesar pentru efectuarea acestei operații,
folosind înmulțirea matriceală. Chiar și după serial
operații algebrice pe mai multe iterații,
mai putem concluziona că această matrice
ar trebui să fie pentru întreaga serie, folosind ceea ce știm despre noi
partea dreapta sistem nou ecuații. După orice
iterații, xB = B-1b și Z = cB B-1b, deci părțile drepte
noul sistem de ecuaţii a luat forma

15.

Din moment ce realizăm aceeași serie
operații algebrice cu ambele părți
set original, pentru a multiplica dreptul și
în partea stângă, folosim aceeași matrice.
Prin urmare,
Forma matriceală dorită a sistemului de ecuații
după orice iterație:

16.

Exemplu: formă matriceală obținută după iterația 2
pentru problema fabricii de sticlă folosind B-1 și cB:

17.

Folosind mărimile xB = B-1 b și Z = cB B-1 b:

18.

Doar B-1 trebuie primit pentru calcul
toate numerele tabelului simplex din original
parametrii sarcinii (A, b, cB). Oricare dintre aceste numere
poate fi obtinut individual ca
De regulă, se efectuează numai înmulțirea vectorială
(un rând pe coloană) în loc de complet
înmulțirea matriceală. Numerele necesare pentru
efectuarea de iterații ale metodei simplex poate fi
primiți după cum este necesar fără a cheltui
calcule inutile pentru a obține toate numerele.

19. Scurtă prezentare a metodei simplex modificate

1. Inițializare: Ca în metoda originală simplex.
2. Iterație: Pasul 1 Determinați elementul de bază (principal) introdus
variabile: La fel ca în metoda originală simplex.
Pasul 2 Determinați variabilele de bază de ieșire: Ca în original
metoda simplex, cu excepția numărării numai a celor necesare pentru
a acestor numere [coeficienții variabilelor de bază introduse în
fiecare ecuație cu excepția ecuației. (0), apoi, pentru fiecare strict
coeficient pozitiv partea dreaptă această ecuație].
Pasul 3 Determinați o nouă soluție OD: obțineți B-1 și setați xB=B-1b.
3. Analiza optimității: Ca și în metoda originală simplex, pt
cu excepția numărării numai a numerelor necesare pentru această analiză,
adică coeficienți ai variabilelor non-bazice (non-bazice) în
Ecuația (0).
La pasul 3 al iterației, B-1 poate fi obținut de fiecare dată când se utilizează
standard program de calculator pentru inversare (inversare)
matrici. Deoarece B (apoi B-1) se schimbă puțin de la o iterație la
alta, este mai eficient sa se obtina un nou B-1 (notat B-1 nou) de la
B-1 în iterația anterioară (B-1 vechi). (Pentru soluția originală OA).

Metoda simplex modificată

În metoda modificată matricea

nu este recalculată, doar matricea este stocată și recalculată. Restul algoritmului este similar cu cel descris mai sus.

1. Calculați variabile duale

2. Verificarea optimității. este convertit în.

Verificarea constă într-un calcul pentru toate coloanele. Coloană cu valoare< 0 можно вводить в базис.

Adesea este aleasă valoarea minimă, dar aceasta necesită iterarea tuturor coloanelor.

Mai des se alege o valoare mai mică decât o anumită valoare specificată

Dacă nu se găsește o astfel de coloană, valoarea absolută maximă găsită este considerată și coloana corespunzătoare este introdus în bază.

3. Definirea ieșirii.

Fie coloana de intrare corespunzătoare variabilei Planul de bază este soluția sistemului Creștere.

Să înmulțim de la stânga cu, i.e.

Aici este planul de bază și este descompunerea coloanei de intrare în funcție de bază.

Găsim valoarea maximă la care toate valorile nu sunt negative. Dacă poate fi luată cât de mare se dorește, soluția nu este limitată. În caz contrar, unul dintre elemente va ajunge la zero. Deducem coloana corespunzătoare din bază.

4. Recalcularea planului de referință (de bază).

Calculăm noul plan de referință folosind formula deja dată cu valoarea găsită.

5. Recalculăm inversul celui de bază.

Fie coloana de ieșire.

Matricea B poate fi reprezentată ca

unde este matricea de bază fără coloana de ieșire.

După înlocuirea coloanei, matricea de bază va arăta ca

Trebuie să găsim o matrice astfel încât

Cometariu.

La recalcularea matricei se acumulează erori de rotunjire. Pentru a evita erorile mari, matricea este recalculată complet din când în când. Acest proces se numește „repetiție”.

Versiune multiplicativă a metodei simplex

În versiunea multiplicativă, matricea nu este stocată, sunt stocați doar factorii

La rezolvarea problemelor economice, matricea de constrângeri este adesea rară, caz în care versiunea multiplicativă devine beneficii aditionale- puteți stoca multiplicatori într-o formă comprimată (nu stocați zerouri).

Alte opțiuni pentru metoda simplex

Pentru a evita acumularea erorilor de rotunjire, se poate folosi descompunerea LU a matricei.

Cu un număr copleșitor de restricții de tip „inegalitate”, se poate folosi metoda pe baza variabila.

Metoda se bazează pe faptul că matricea de bază poate fi reprezentată în formă

Inversul său are forma

Cu dimensiuni relativ mici ale matricei, restul matricei poate să nu fie stocat.

Această abordare poate rezolva probleme cu zeci de milioane de linii de constrângeri (de exemplu, din teoria jocurilor).

Metoda dual simplex

Pentru implementare metoda duala este necesar să trecem de la problema minimă la problema maximă (sau invers) prin transpunerea matricei coeficienților. Când treceți de la o sarcină la minim funcție obiectivă va lua forma:

sub restricții

Teorema dualității. Dacă dintr-un cuplu probleme duble unul are plan optim, atunci atât celălalt are o soluție, iar valorile extreme ale funcțiilor liniare ale acestor probleme sunt egale.

Dacă funcție liniară una dintre probleme nu este limitată, atunci cealaltă nu are soluție.