Soluția problemei de programare liniară prin metoda simplex

Soluția soluției lineare
programarea prin metoda simplex
Ladover Tatyana Mikhailovna
Colegiul de Inginerie Civilă și Economie din Novorossiysk


O trăsătură distinctivă ZLP care formează subsetul de probleme de programare matematică, este că obiectivul problemei este scris ca o funcție liniară f (X) și, de asemenea, constrângerile liniare.







Sarcina principală a programării liniare este de a găsi
astfel de valori ale variabilelor X = (x1, x2, x3, ..., xn) care conduc țintă
funcția f (X) la o valoare extremă.

Vederea generală a înregistrării modelului LPP:

xi ≥ 0, i = 1 ÷ n sunt cantitățile necunoscute,
AIJ. bj. ci sunt date constante,
bj - stocuri de materii prime, energie, etc. j = 1 ÷ m.


Colecția de numere X = (x1, x2, x3, xn) satisfăcând constrângerile
o soluție sau un plan sau o zonă permisă
(SDT).

O soluție fezabilă care maximizează sau minimizează funcția obiectivă se numește o soluție optimă sau un plan optim.

În cazul special, în prezența a două variabile, se poate rezolva grafic LPA.
Dacă există mai mult de două variabile în LP, cea mai simplă metodă este cea mai comună metodă de soluționare.
Un simplex este o expresie a formei
c1 x1 + c2 x2 + ... + cn xn
sau suma produselor pereche de vectori

Metoda de rezolvare a problemelor cu f (x) → min diferă de metoda de rezolvare a problemelor c f (x) → max. Pentru facilitarea rezolvării problemelor ambelor tipuri printr-un singur algoritm, modelele lor trebuie reduse la așa-numitele forma canonică (CF).

Se crede că APL este scris în formă canonică dacă:
a) funcția obiectivă este maximizată;
b) constrângerile problemei au forma egalității cu partea non-negativă (bj ≥ 0);
c) toate variabilele din modelul problemei sunt non-negative (≥ 0).


Astfel, forma canonică a modelului APL este:

Să luăm în considerare două tipuri de modele matematice ale APL.
I.
Să menționăm CF al ZLP dat de modelul în care toate constrângerile formei ≤:


În toate inegalitățile sistemului de constrângere, partea stângă este mai mică sau egală cu cea din dreapta (≤). Pentru a le egaliza (conform formularului canonic), este necesar să adăugați în partea stângă a fiecărei restricții. respectiv, variabilele întregi ne-negative xn + 1, xn + 2, ..., xn + m. Că valoarea funcției obiective nu sa schimbat, aceste variabile sunt introduse în ea cu coeficienți zero.
astfel după reducerea la forma canonică a noastră
sarcina va arata ca:

Dacă constrângerea modelului matematic inițial al problemei este dată de semnul egalității stricte (=), atunci nu se introduce o variabilă suplimentară în ea, ci doar o variabilă artificială (vezi mai jos).

Lăsați problema economică să fie descrisă de următorul model


Să aducem acest model matematic la KF:

II.
Considerăm al doilea caz special: f (x) → min și cel puțin una din constrângerile formei ≥ (sau chiar toate). Modelul acestei probleme are forma:

Definirea valorii minime a funcției f (x) poate fi redusă la găsirea valorii maxime a funcției -f (x).
astfel în astfel de cazuri, coeficienții pentru necunoscuți în f (x) → min trebuie multiplicați cu (-1).
Pentru a aduce la egalitate strictă constrângerea formei ≥, este necesar să se scadă din partea stângă a fiecărei restricții de acest fel. respectiv, variabilele întregi ne-negative xn + 1, xn + 2, .... xn + m.
Apoi, după reducerea la CF, problema (**) va avea forma:

Toate variabilele din modelul matematic sunt împărțite în două tipuri:


- de bază (dependentă), care poate fi exprimată prin toate celelalte
variabile. O variabilă este de bază dacă este inclusă
numai într-una din ecuațiile sistemului cu un coeficient egal cu 1 (deci în sistem (*) variabilele de bază sunt x3 .x4. x5).
- toate celelalte variabile sunt ne-independente (independente).

O soluție particulară, găsirea variabilelor de bază atunci când ecuația variabilelor non-vanishing la zero (xi = 0) se numește variabila de bază. Se spune că o soluție de bază este degenerată dacă cel puțin una dintre variabilele de bază este 0, o astfel de problemă fiind considerată a fi degenerată. În caz contrar, se spune că problema este nondegenerată.








Mai sus am analizat două cazuri speciale I și II.
În cazul I, soluția de bază este o soluție admisibilă:

și nu este permis, deoarece contrazice condiția de non-negativitate a variabilelor (xi ≥ 0).


În astfel de cazuri, metoda bazei artificiale este utilizată pentru a izola variabilele de bază și pentru a găsi o soluție acceptabilă, care constă în următoarele:
1) în fiecare restricție a formei ≥ sau = introduceți o variabilă artificială non-negativă y1. y2, ... ym;
2) variabilele artificiale intră în funcția obiectivă cu coeficientul (-M), unde M este un număr foarte mare pozitiv (de aici și metoda M-a).

După introducerea variabilelor artificiale, QF a problemei (**) va avea forma:


Set de variabile artificiale y1. y2, ..., ym în metoda M formează o bază artificială. Variabilele artificiale sunt introduse doar pentru a obține planul inițial de bază pentru rezolvarea problemelor LP prin metoda simplex. Este convenabil să se ia decizia APL în așa-numitele tabele simplex în forma următoare:


Valoarea funcției obiectiv f (x) este calculat ca suma produselor elementelor și elemente ale coloanei C. Coloana B. Evaluarea relativă pereche - ca sumă a produselor de elemente de perechi C și elemente de coloană coloană numărul i corespunzătoare.

Algoritm pentru rezolvarea metodei simplex prin metoda simplex

1. Dă-o matematică
model în forma canonică. Umpleți tabelul simplex și calculați valorile
funcția obiectivă și estimările relative.

2. - dacă toate sunt relative
estimările sunt nonnegative, iar printre variabilele de bază nu există nici unul artificial, planul
este optim; problema este rezolvată. Soluția se găsește în coloana B:

- Dacă toate evaluările relative non-negative, iar între ele este egal cu zero, și nu există nici, atunci problema este rezolvată de om, și are un număr infinit de soluții, dintre care unul a venit în baza (situată în coloana B) între variabilele de bază;

- Dacă toate estimările relative sunt nonnegative, dar printre variabilele de bază sunt artificiale, atunci problema nu are soluții;

- dacă între rude
estimările sunt negative, atunci soluția problemei nu este optimă, o tranziție spre
următorul plan de bază (la clauza 3).


3. Din toate estimările relative negative, cel mai mare din modul este ales. Coloana corespunzătoare se numește coloana principală. Pentru a determina linia principală, trebuie să separăm separat coloana B în coloana principală
(zerouri și numere negative ale coloanei principale nu sunt divizibile). Cel mai mic privat
corespunde liniei principale. La intersecția dintre linia principală și coloana principală
este elementul principal al tabelului simplex. Acest număr poate fi numai
pozitiv.

Apoi, trebuie să recalculați masa.


4. În tabelul nou, variabilele rândului principal și ale coloanei principale (împreună cu coeficienții lor) sunt schimbate. Variabilele rămase și coeficienții acestora sunt suprascrise fără modificări.
În locul elementului principal, se scrie numărul invers: 1 / elementul principal.
Elementele coloanei principale a tabelului vechi sunt împărțite în (- elementul principal).
Elementele liniei principale a tabelului vechi sunt împărțite în (elementul principal).
Toate celelalte elemente sunt recalculate în conformitate cu regula dreptunghiului:
din produsul elementelor diagonalei principale care trece prin elementul principal, se scade produsul elementelor diagonalei secundare și se împarte rezultatul cu elementul principal; Numărul rezultat este înscris în celula corespunzătoare din tabela simplă nouă. Dacă în rândul principal sau în coloana principală există zerouri, atunci
elementele corespunzătoare acestor zerouri ale coloanei și liniile sunt suprascrise fără
modificări la noul tabel.


5. Noul tabel calculează valorile funcției obiectiv și relativă
evaluări. Trecerea la punctul 2.

Exemplul 2.
Rezolvăm următoarea problemă prin metoda simplex.


Stăpânul face două tipuri de linguri Melchior: fără a fi urmărit (L1) la un preț de 2 euro și cu monedă (L2) la un preț de 3 euro. În timpul zilei, comandantul nu are mai puțin de o lingură. Stocul zilnic de materii prime nu este mai mare de 12 dm 3. în timp ce o lingură de tipul L1 este de 3 dm 3. și o lingură de tipul L2 - 2 dm 3 din argintul de nichel.
Care este profitul maxim pe zi pe care maestrul îl poate aștepta dacă se respectă standardele specificate?

Denumește după:
x1 este numărul de linguri de tip L1,
x2 este numărul de linguri de tip A2.

Prin condiția problemei, vom compila modelul său matematic:
venitul din vânzarea de linguri de tip L1 va fi de 2 * x1 (euro);
Venitul din vânzarea de linguri de tip L2 va fi de 3 * x1 (euro). Suma acestor numere este egală cu venitul comandantului - funcția obiectivă.
Producerea de linguri de tip A1, a petrecut 3 * x1 m dm 3 de argint nichel, iar producția de linguri de tip A2 petrecut 2 * x1 dm 3 m și expertul nu poate fi utilizat în ziua de mai mult de 12 dm 3. M - aceasta este prima restricție. Din condiția că maestrul face cel puțin o lingură pe zi, notăm a doua restricție și obținem modelul problemei:

Pentru a rezolva problema prin metoda simplex, reducem modelul matematic la forma canonică:

Pe baza formei canonice, construim planul inițial de bază al problemei:


Sarcina nu este rezolvată, deoarece În baza există variabile artificiale, iar printre estimările relative - negative. Printre relativă negativă otsenokmso-Fareast-font-family: Calibri; mso-ansi-language: RU; mso-Fareast-language: EN-US;
alege modulul cel mai mare (-M-3) - corespunde coloanei principale; găsi rând acasă (al doilea, t.k.1 / 1 scor relativ negativ singur (-3), corespunde coloanei principale; linia principală - primul, respectiv, elementul principal este egal cu doi (celula evidențiată în albastru) completarea tabelelor de recalculare a muta pe. la un nou plan de bază.


Toate estimările relative sunt non-negative, nu există variabile artificiale în bază, prin urmare, problema este rezolvată.


soluţie:
X1 = 0 (deoarece această variabilă nu a ajuns la baza), X2 = 6 a ieșit pe bază, venitul maxim pentru un astfel de plan de ieșire este

f (X) = 2 * 0 + 3 * 6 = 18 (euro).

2 Malik GS Bazele economiei și metodele matematice în planificare / - M. Vysshaya Shkola, 1988.-
279 sec.







Articole similare

Pagina anterioară

Pagina următoare

Trimiteți-le prietenilor: