Metoda simplex modificată pentru rezolvarea problemelor de programare liniară

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)
reprezintă numărul normal 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
secvență 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
simplex modificat-metoda - cum
găsește o nouă soluție OD după ce o definește
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 nebazice 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 în 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 sursă
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ă episod
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 și î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 pt
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ții 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 pe iterația anterioară(B-1 vechi). (Pentru soluția originală OA). Să explicăm calculele a i , j ¢ folosind „regula dreptunghiului”. Este necesar să luați elementul de activare ak, sși conectați-l mental cu coeficientul a cărui nouă valoare doriți să găsiți. Această linie ar trebui considerată diagonala principală; pe ea este construit un dreptunghi, ale cărui laturi sunt rânduri și coloane. Trebuie să desenați o diagonală secundară în dreptunghi, apoi valoarea noului coeficient va fi egală cu valoarea sa inițială, din care se scade produsul elementelor situate pe diagonala secundară împărțit la elementul de rezolvare. Să explicăm aceste acțiuni în diagramă (Fig. 1.9). Înainte de a completa tabelul simplex, ecuațiile originale trebuie prezentate în forma (1.21).

	a k,j
			a i,j

Să ne uităm la esența transformărilor metodei simplex folosind exemplul 1.4. Să ne amintim inegalitățile de constrângere și funcția obiectivă din acest exemplu și să găsim max funcție obiectiv folosind metoda de mai sus:

F = 908X 1 + 676X 2 ® max.

X 1 + X 2 14,

X 2 10,

10 X 1 + 8 X 2 120,

7X 1 + 5 X 2 70,

4X 1 + 2X 2 28,

.

Să o transformăm în formă canonică prin introducerea unor variabile suplimentare X j 0 și transformând inegalitățile în egalități. Trebuie remarcat faptul că, dacă există un semn „” în inegalitate, atunci cu o variabilă liberă se scrie „-”, în caz contrar - „+”:

X 1 + X 2 = 14 - X 3,

X 2 = 10 - X 4,

10 X 1 + 8 X 2 = 120 - X 5,

7X 1 + 5 X 2 = 70 - X 6,

4X 1 + 2X 2 = 28 - X 7.

Pentru a începe procedura metodei simplex, mai întâi trebuie să găsiți o soluție de referință din setul de soluții de bază ale sistemului de ecuații rezultat. Luând în considerare acest lucru, există trei etape în rezolvarea problemelor folosind metoda simplex:

Găsirea soluției de bază inițiale și formarea tabelului simplex inițial;

Determinarea unei soluții acceptabile;

Determinarea soluției optime.

etapa 1

Iniţială solutie de baza sisteme pe care le găsim prin asumarea variabilelor libere X 1Și X 2 .

Apoi X 3 = 14 - X 1 - X 2,

X 4 = 10 - X 2,

X 5 =120 - 10X 1 - 8X 2,

X 6 = 70 - 10X 1 - 5X 2,

X 7 = 28 - 4X 1 - 2X 2,

F = 908X 1 + 676X 2 = 0.

Să transformăm aceste ecuații în aspect normal:

X 3 = 14 - (X 1 + X 2),

X 4 = 10 - (0X 1 + X 2),

X 5 =120 - (10X 1 + 8X 2),

X 6 = 70 - (7X 1 + 5X 2),

X 7 = 10 - (4X 1 + 2X 2),

F = 0 + 908 X 1 + 676 X 2.

Scriem sistemul de ecuații rezultat sub forma tabelului simplex original (Tabelul 1.9). În tabel 1.9 nu există termeni liberi negativi. În consecință, am obținut o soluție suport (admisibilă), deoarece o soluție admisibilă este orice soluție nenegativă (pentru care > 0 ), dar nu este optim.

Evident, dacă pentru toate necunoscutele din funcția obiectiv F Dacă coeficienții ar fi pozitivi, atunci valoarea maximă ar fi atinsă F. Din aceasta rezultă semnul optimității unei soluții admisibile: V F- rândul tabelului simplex nu trebuie să aibă coeficienți negativi.

Tabelul 1.9

Variabile de bază X b	Membru gratuit	Variabile libere
X 1	X 2
X 3
X 4
X 5
X 6
X 7
F		- 908	- 676

a 2-a etapă

Să reamintim că operația principală a metodei simplex este în esență aceea că o variabilă de bază este înlocuită cu o variabilă liberă. . În acest caz, operațiunea de înlocuire se efectuează în următoarele condiții:

Valoarea funcției obiective F noua soluție de referință (admisibilă) trebuie să fie mai mare decât cea anterioară;

Noua soluție a sistemului trebuie să fie și de referință (admisibilă).

În exemplul nostru, prima condiție este îndeplinită dacă elementul de activare este pozitiv și este selectat în coloana coeficientului negativ F-linii.

A doua condiție este îndeplinită dacă elementul de rezoluție este găsit ca raport pozitiv minim dintre elementele coloanei cu membri liberi și elementele corespunzătoare ale coloanei de rezoluție.

Conform regulii enunțate mai sus, pentru a găsi o soluție admisibilă, variabilele de bază și libere sunt schimbate. Pentru a face acest lucru, găsiți un element de rezolvare (este încadrat în Tabelul 1.9). În cazul nostru, coloana permisivă ar trebui să fie ca X 1 , asa de X 2. Împărțirea variabilelor libere la valorile corespunzătoare X 1Și X 2 (cu excepția liniei F), găsim cea mai mică valoare pozitivă. Este important de reținut că pentru coloană X 1 :

Este important de reținut că pentru coloană X 2:

Cel mai mic raport 28/4 definește rândul de rezolvare și coloana de rezolvare, iar intersecția coloanei de rezolvare și rândul de rezolvare este elementul de rezolvare un ks= 4. În tabel. 1.9 marchem coloana de autorizare și rândul de permise cu săgeți (®). După ce a hotărât un ks, construiți următorul tabel, în care variabilele incluse în rândul și coloana elementului de rezolvare sunt schimbate ᴛ.ᴇ. converti variabilele de bază în variabile libere, iar cele libere în variabile de bază.

În exemplul nostru, schimbăm variabilele X 7 Și X 1 , notat în tabel. 1,9 săgeți. Coeficienții noului tabel. 1,10 se găsește din coeficienții vechiului tabel. 1.9, folosind expresiile date în tabel. 1.8 și „regula dreptunghiului”. În tabel Din nou 1.10 nu avem o soluție optimă.

Tabelul 1.10

Variabile de bază X b

Membru gratuit B

Variabile libere

X 7

X 2

X 3

- 1/4

1/2

X 4

X 5

-5/2

X 6

-7/4

3/2

X 1

1/4

1/2

F

-222

Conform regulilor descrise mai sus în tabel. 1.10 găsim elementul de rezolvare 1 și construim un nou tabel. 1.11 prin înlocuirea bazei ( X 4Și X 2). Subliniem în special faptul că pentru a găsi elementul de rezolvare trebuie să alegem cea mai mică valoare pozitivă, ᴛ.ᴇ. Nu luăm în considerare relațiile negative ale termenilor liberi cu coeficienții coloanei de rezoluție.

a 3-a etapă

Să verificăm dacă soluția găsită este optimă, iar pentru exemplul nostru - maximă. Pentru a face acest lucru, vom analiza funcția obiectiv F: F = 8576 + 227 X 7 + 222 X 4.

Funcția obiectiv nu conține coeficienți negativi și are cea mai mare valoareÎn ultimul tabel, am obținut soluția optimă:

X3 = 2; X2 = 10; X5 = 20; X6 = 6; X1 = 2; X7 = X4 = 0;

F max = 8576.

Vă rugăm să rețineți că rezultatele rezolvării metodei simplex și a metodei grafice sunt aceleași.

În conformitate cu secvența considerată, algoritmul metodei simplex trebuie să aibă următoarele blocuri:

1. Găsirea soluției inițiale de bază (de referință) și formarea tabelului inițial.

2. Găsirea elementului de rezolvare un ks(găsirea termenului liber negativ - b i < 0 и минимального отношенияb i / a ij; Dacă nu există coeficienți negativi în rândul termenului liber negativ, atunci problema este de nerezolvat).

3. Recalcularea masa noua conform formulelor din tabel. 1.8.

4. Verificarea prezenței unui termen liber negativ. Dacă există, treceți la pasul 2. Absența unui termen liber negativ înseamnă că a fost obținută o soluție de referință (admisibilă).

5. Similar pașilor 2 - 4, tabelul este recalculat atunci când se caută soluția optimă.

Rezolvarea problemei LP folosind metoda simplex sub formă de matrice

Necesar pentru a minimiza ,

sub restricții

la " X³ 0.

Să introducem vectorii:

C= (C 1 , ... , C n) - vector de estimări,

X= (X 1 , ... , X n) - vector de variabile,

b= (B 1 , ... , B m) - vector de restricții

și matrice

A=

dimensiune (mn) - matricea coeficienților de constrângere.

Atunci problema LP va avea următoarea interpretare:

minimiza F=CX

in conditii AX = b, X 0.

Această problemă poate fi scrisă sub formă de matrice:

Să introducem notația:

A * = - aici este matricea A* dimensiune (m+1)(n+1).

Conform metodei de mai sus, se găsește elementul de rezolvare un ks.

Urmatorul pas metoda simplex - o procedură de eliminare gaussiană care vă permite să faceți toți coeficienții în s- m coloana, cu excepția un ks, zero, un ks- egal cu unu.

Este important de reținut că pentru metoda simplex sub formă de matrice, iterația metodei simplex este echivalentă cu înmulțirea ecuației matriceale din stânga cu următorul matrice pătrată:

(1.23)

, Unde k 0; s 0.

Dacă toate coloanele matricei Aîmpărțiți în de bază Bși nebază N, atunci problema LP poate fi scrisă după cum urmează:

,

Unde CbȘi C N- componentele vectoriale corespunzătoare C, X b, X N- variabile de bază și nebaze.

Pentru a selecta variabilele de bază inițiale x b ar trebui să înmulțiți ecuația din stânga cu matricea:

Unde R= CbB-1.

Ca rezultat obținem

,

Unde eu- matrice de identitate.

Rezultă că estimări relative pentru variabile nebazice

c j = c j - C b B -1 a j = c j - Ra j .

Baza va fi admisibilă dacă termenii liberi ai variabilelor de bază sunt nenegativi, ᴛ.ᴇ. B -1 b ³ 0.

Dacă c j³ 0 pentru , atunci baza este soluție optimă sarcini. Vectorul se numește vectorul prețului curent. Fiecare rând este înmulțit cu un vector Rși se scade din linia coeficientului de cost pentru a elimina coeficienții de cost pentru variabilele de bază.

Dacă problema LP nu este specificată în formă canonică, ᴛ.ᴇ.

minimiza F=CX

in conditii AX b , X 0,

apoi, introducând variabile slabe, acestea pot fi scrise sub formă

Metoda de eliminare a rândurilor pentru o matrice este echivalentă cu înmulțirea acelei matrice din stânga cu B-1, Unde B- baza submatricelor A, Apoi

,

ᴛ.ᴇ. matrice obţinută în locul matricei identitare eu, va fi matricea inversă pentru baza curentă. Scorurile relative situate deasupra matricei de identitate vor fi

,

deoarece sunt vectori unitari.

Deoarece F= C b B -1 b = Rb, valoarea curentă a funcției obiectiv este egală cu produsul vectorului prețurilor curente al matricei A la vectorul original b.

Exemplu.
Postat pe ref.rf
F = 5X 1 + 6X 2 + 3X 3 + 4X 4 + 5X 5® min

sub restricții

2X 1 + 3X 3 + 4X 4 + 2X 5 = 10 ,

3X 2 + 3X 4 + 6X 5 = 9,

.

Pentru acest exemplu matrice A* va arăta ca

.

Lăsa X 1Și X 2- variabile de bază.

Matrice B se pare ca

.

Apoi matricea inversă B-1 Are următoarea vedere

.

Să vă reamintim că , unde matricea adjunctă compusă din complemente algebrice de elemente b ik determinant al matricei B.

Determinantul este egal cu:

= .

Prin urmare, matricea B Nimic special.

Adunări algebrice elementele determinantului au următoarele semnificații:

b 11 = 3, b 12 = 0, b 12 = 0, b 22 = 2; acestea . .

Înmulțind cu , găsim matrice inversă:

.

Vectorul preţurilor curente va fi

R = C b B -1 = = .

Să vă reamintim că Cb- componente ale vectorului de bază C:

Apoi = .

Pentru a selecta baza inițială aveți nevoie de o matrice A*înmulțiți la stânga cu matrice

=

.

Elementul de rezolvare este într-un pătrat.

O iterare a metodei simplex este echivalentă cu tabelul rezultat înmulțit din stânga cu următoarea matrice:

.

Această matrice este obținută din matricea (1.23)

Aici aks = 2;

a 11 = 1; a 12 = - a 0s / a ks = - 12/2 = - 6;

a 13 = 0 ; a 21 = 0 ; a 22 = 1/ a ks = 1/2 ; a23 = 0;

a 31 = 0 ; a 32 = - a ms / a ks = -1/2 ; a 33 = 1.

Atunci noi avem

=

(1.24)

Elementul de rezolvare este plasat într-un pătrat.

Următoarea iterație a metodei simplex este echivalentă cu înmulțirea la stânga cu matrice

.

=

.

Prin urmare, Fmin =11; X 4=7/3; X 5=1/3; X 1 =X 2 =X 3=0.

Metoda simplex modificată (MSM) diferită de metoda simplex obișnuită (CM) pentru că în CM Toate elementele tabelelor simplex sunt recalculate la fiecare iterație și când se obține următorul tabel, toate tabelele anterioare, inclusiv cel original, nu sunt salvate. ÎN MSM tabelul inițial este salvat și la fiecare iterație se determină următoarele: un rând de estimări relative C introduse în bază și valoarea curentă a vectorului părților din dreapta ale constrângerilor. Pentru a determina toate elementele tabelului după j- a iterație CM, este suficient să cunoaștem matricea B-1, corespunzând acestui tabel, matricea originală și indici ai variabilelor de bază curente. Apoi vectorul curent R = C b B -1(indicii variabilelor de bază curente determină ce elemente ale vectorului estimărilor din tabelul sursă sunt incluse în vector C b); =B -1 b, Unde b este preluat din tabelul original și orice coloană a noului tabel = B-1A j , Unde A j - coloana tabelului sursă.

Să fie dat acum tabelul sursă B-1, corespunzător tabelului i a iterație. Pentru a obține matricea B-1, corespunzătoare (i+1)- a treia iterație, trebuie să definiți o coloană non-bază i tabelul care ar trebui introdus în bază. Din CM rezultă că trebuie introdusă în temei dacă C j<0. Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, крайне важно вычислить C j Pentru i tabelele, alegeți dintre ele<0, а затем вычислить

A S = B-1și = B -1 b (= C j - Ra j ).

După ce am găsit elementul de rezolvare și folosind elementele vectorilor și , găsim matricea B-1 pentru următorul tabel.

Exemplu. Folosind metoda simplex modificată pentru a minimiza

F = 5X 1 + 6X 2 + 3X 3 + 4X 4 + 5X 5 ® min

cu restrictii:

2X 1 + 3X 3 + 4X 4 + 2X 5 = 10,

3X 2 + 3X 4 + 6X 5 = 9,

Alegerea ca variabile de bază X 1Și X 2, am primit următoarea sarcină: F = 43 - 9/2X 3 - 12X 4 - 12X 5

3. Metoda simplex modificată

Acest tip de metodă simplex se bazează pe caracteristicile algebrei liniare care permit să lucrăm cu o parte din matricea de constrângeri atunci când rezolvăm o problemă. Uneori metoda se numește metoda matricei inverse.

În timpul funcționării algoritmului, matricea de constrângeri este inversată spontan în părți corespunzătoare vectorilor de bază actuali. Această abilitate face ca implementarea calculelor să fie foarte atractivă datorită economisirii de memorie pentru variabilele intermediare și a reducerii semnificative a timpului de calcul. Această capacitate este bună pentru situațiile în care numărul de variabile n depășește semnificativ numărul de constrângeri m.

În general, metoda reflectă caracteristicile tradiționale ale abordării generale a rezolvării problemelor de programare liniară, inclusiv canonizarea condițiilor problemei, calculul diferențelor simplex, verificarea condițiilor de optimitate, luarea deciziilor pe bază de corecție și eliminarea Jordan-Gauss. Caracteristicile includ prezența a două tabele - cele principale și auxiliare, ordinea în care sunt completate și o anumită specificitate a formulelor de calcul.

Cunoscând planul optim pentru această problemă, pe baza relațiilor obținem planul optim pentru problema inițială.

Astfel, procesul de găsire a unei soluții la o problemă de programare neliniară include următorii pași:

1. Problema originală se reduce la o problemă de programare liniară.

2. Găsiți o soluție la o problemă liniară

Folosind relații, determinați planul optim pentru problema inițială și găsiți valoarea maximă funcție obiectivă problemă neliniară.

Prima etapă: Primirea sarcinilor pentru cursuri

1. Toate datele numerice referitoare la procesele de producție și economice propuse sunt preluate pe baza unui cod din șase cifre:

Sub fiecare număr literele a, b, c, d, e, f sunt scrise sub următoarea formă:

din ultimul rând al tabelului sarcinilor individuale găsim coloanele corespunzătoare literelor a, b, c, d, e, f. Apoi datele numerice necesare pentru a finaliza acest lucru de curs vor fi datele situate în a - acea coloană din rândul 9, b - acea coloană din rândul 5, c - acea coloană din rândul 5, d - acea coloană din rândul 8, e - coloana de volum din rândul 7 și f – acea coloană din rândul 2.

Conform tabelului sarcinilor inițiale pentru orice variantă de sarcini din coloana a, executantul primește varianta sarcinii care se execută. În cazul meu, numărul 9 corespunde opțiunii 9.

O anumită plantă produce trei tipuri de produse și consumă două tipuri de resurse. Funcția de producție a fiecărui tip de produs la întreprindere este descrisă prin egalități:

unde C i și sunt valori constante, i = 1, 2, 3;

X 1 – resurse de muncă în zile-om;

X 2 – resurse monetare şi materiale, în tenge;

Y i este produsul rezultat

X 1 = a 1 x 1 + b 1 x 2 + c 1 x 3

X 2 = a 2 x 1 + b 2 x 2 + c 2 x 3

Găsiți toate soluțiile de bază nenegative și determinați planul optim F = y 1 + y 2 + y 3.

Se știe că pentru producția de j – acel tip de produs, a ij unități de i – acea resursă sunt cheltuite. Aceste costuri sunt prezentate în tabelele 3.9.1. – 3.9.10

Datele numerice ulterioare sunt preluate numai din tabelul de date sursă al opțiunii de sarcină selectată, de exemplu. din tabelul nr 3.9.11.

2. Conform coloanei tabelului nr. 3.9.11 pentru rândul 8, tabelul inițial al costurilor unităților de resurse va fi tabelul nr. 3.9.4 i.e. următorul tabel:

Resursele produselor
eu	8	4	6
II	160	240	200

3. Folosind coloana c – pe linia 3 găsim cu 1 =6, α 1 =0,6

4. Folosind coloana d – pe linia 5 determinăm cu 2 =5, α 2 =0,5

5. Folosind coloana e – linia 4, stabilim că c 3 =8, α 3 =0,4.

6. Și în sfârșit, folosind coloana f - în linia 1 găsim T zile persoane = 1000, P tenge = 280000

Pentru producţie există resurse de muncă T man zile şi resurse monetare P tenge.

Este necesar să se găsească planul optim de producție la care produsul de ieșire va fi cel mai mare.

A doua etapă este elaborarea unui model matematic al problemei

1. Pe baza datelor inițiale obținute în prima etapă și a descrierii procesului de producție dat, se întocmește următorul tabel:

Resursele produselor
eu	8	4	6	1000
II	160	240	200	280000

Fie X 1 să desemneze resurse de primul tip.

Fie X 2 resurse de tip II.

2. Revenind la condițiile problemei, determinăm toate restricțiile posibile, combinându-le într-un sistem de restricții.

8Х 1 + 4Х 2 + 6Х 3 ≤ 1000

240Х 1 + 200Х 2 + 160Х 3 ≤ 280000

Astfel, avem o problemă de programare neliniară. Astfel de probleme se numesc probleme de programare neliniară.

Problemele de programare neliniară sunt rezolvate prin reducerea lor la probleme de programare liniară.

Pentru rezolvarea problemei de programare liniara se foloseste metoda simplex.

A treia etapă este alegerea unei metode de rezolvare a problemei matematice rezultate

1. Pentru a rezolva probleme de programare liniară folosind metoda simplex, problema se reduce la forma canonică:

8X 1 + 4X 2 + 6X 3 + X 4 = 1000

240Х 1 + 200Х 2 + 160Х 3 + Х 5 = 280000

Sunt în curs de dezvoltare metode de găsire a valorilor extreme ale funcției obiectiv între setul de valori posibile ale acesteia determinate de constrângeri. Prezența restricțiilor face problemele de programare matematică fundamental diferite de problemele clasice de analiză matematică de găsire a valorilor extreme ale unei funcții. Metode de analiză matematică pentru căutarea extremului unei funcții în probleme...

Găsirea punctului Kuhn-Tucker oferă o soluție optimă pentru problema de programare neliniară. Teorema 2 poate fi folosită și pentru a demonstra optimitatea unei soluții date la o problemă de programare neliniară. Pentru a ilustra, luați în considerare din nou exemplul: Minimizarea sub constrângeri Folosind teorema 2, demonstrăm că soluția este optimă. Avem deci...

Razele care emană dintr-un punct se numesc con convex poliedric cu un vârf într-un punct dat. 1.4 Fundamente matematice pentru rezolvarea grafică a problemelor de programare liniară 1.4.1 Aparatură matematică Pentru a înțelege totul mai departe, este util să cunoaștem și să ne imaginăm interpretarea geometrică a problemelor de programare liniară, care poate fi dată pentru cazurile n = 2 și n = ...

Dacă punem variabilele de bază curente într-un astfel de tabel simplex egal cu Ai,0, iar pe cele libere egale cu zero, atunci se va obține o soluție optimă. Practica utilizării metodei simplex a arătat că numărul de iterații necesare pentru a rezolva o problemă de programare liniară variază de obicei între 2m și 3m, deși pentru unele probleme special construite, calculele conform regulilor metodei simplex se transformă în direct...

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

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

O metodă geometrică pentru rezolvarea problemelor standard de programare liniară cu două variabile. O metodă universală de rezolvare a problemei canonice. 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. Recalcularea unui tabel simplex folosind metoda Jordan-Gauss. Întocmirea unui model al unei probleme de transport.

test, adaugat 18.02.2014


Model economico-matematic pentru obtinerea profitului maxim, rezolvarea acestuia prin metoda grafica. Algoritm pentru rezolvarea unei probleme de programare liniară folosind metoda simplex. Întocmirea unei probleme duale și soluția ei grafică. Soluție matrice de plată.

test, adaugat 05.11.2014


Fundamentele modelării matematice a proceselor economice. Caracteristici generale ale metodelor 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


Întocmirea unui model matematic al problemei. Calculul planului optim de transport cu costul minim folosind metoda potențială. Opțiunea optimă pentru echipamentele mobile speciale pentru suportul tehnic al managementului producției.

test, adaugat 06.01.2014

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ă o astfel de coloană nu este găsită, 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 Plan 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 opțiunea multiplicativă primește avantaje suplimentare - 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, poate fi utilizată 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 implementarea metodei duale este necesar să trecem de la problema minimă la problema maximă (sau invers) prin transpunerea matricei coeficienților. La trecerea de la problemă la minim, funcția obiectiv ia forma:

sub restricții

Teorema dualității. Dacă una dintr-o pereche de probleme duale are un plan optim, atunci cealaltă are o soluție, iar valorile extreme ale funcțiilor liniare ale acestor probleme sunt egale.

Dacă funcția liniară a uneia dintre probleme este nemărginită, atunci cealaltă nu are soluție.