Orice problema de programare liniară (LP), indiferent de înregistrare poate fi redusă la standard și forma canonică și rezolvată prin metoda simplex, care într-un sens este o metodă universală pentru PL. Metoda C algoritm este iterativ în natură.
O soluție fezabilă a problemei LP este declarat a fi orice soluție de constrângeri (4.3) care satisface condițiile nu este negativitate
În probleme industriale, modele matematice sunt investigate prin metodele de LP, întotdeauna pe variabilele Xj (j =) a impus o cerință nu variabile negative.
Simplex - metoda se bazează pe faptul că, în cazul în care matricea are m rânduri restricții și ele sunt liniar independente, atunci există un set de coloană m, numită bază, care sunt, de asemenea, liniar independente. Setul de valori variabile corespunzătoare unei coloane de bază, numită o soluție de bază (program de suport al deciziei de referință). Dacă restricțiile sistemului - ecuații conținute n variabile Xj (j =) și rangul său este egal cu m, metoda simplex pe fiecare iterație se găsesc valori m variabile de bază care satisfac m constrângerile liniare și n rămase - m variabilă numită liberă și egală cu zero .
Metoda Simplex permite trecerea de la o soluție de bază la alta prin substituirea pentru fiecare iterație a unei coloane în baza pentru o coloană nonbasic atâta timp cât nu există nici o soluție fezabilă este găsit că satisface max (min) a funcției obiectiv. Această soluție se numește optimă.
O interpretare geometrică a simplex - metoda în cazul în care condițiile problemei LP sunt coerente, atunci domeniul soluțiilor fezabile formează un poliedru convexă în spațiul I-dimensional. În acest caz, cea mai bună soluție, în cazul în care există, în mod necesar atins la un vârf al poliedrului. Pentru a găsi o soluție la problema LP, un plan corespunzător vârfurile poliedru de soluții fezabile este suficient pentru a rezolva (de sprijin, planuri de bază).
C - metoda permite o ordonată nodurile de sortare a poliedrului. După stabilirea unuia dintre nodurile, această metodă ajută să se stabilească dacă a găsit optim planul t. E. Fie că a făcut în partea de sus a valorii extremă a funcției obiectiv. Dacă planul suboptimal, apoi a făcut trecerea la un nod învecinat al poliedrului, care oferă nu mai puțin de valoare (nu mai mult) a funcției obiectiv.
Cu aparatul de lucru - metoda sunt tabelul simplex. Secvențial se deplasează de la o masă la alta, ca rezultat vom obține soluția optimă.
Pentru a rezolva problema metodei-tabel simplex, trebuie să-l prezinte într-o formă canonică, adică. E. În unitatea de control trebuie să fie semne de „egal“, dreptul numerelor non-negativ, precum și toate cerințele variabile impuse nu este negativitate.
Dacă sistemul conține constrângeri de inegalitate, fiecare inegalitate să fie convertite în ecuația prin introducerea de variabile suplimentare sau bilanț. Acestea sunt introduse într-o singură variabilă în fiecare inegalitate cu semnul „+“ în cazul în care inegalitatea este semnul £, iar semnul „-“ în cazul în care inegalitatea este un semn ³. De obicei, numerotarea continuă numerotarea variabilelor bilanțului variabilelor de bază ale problemei. Aceste aceleași variabile cu coeficienți zero sunt introduse în funcția obiectiv.
Sistemul inițial de ecuații este util pentru a înregistra în formă vectorială:
Pentru a construi un tabel simplex 1 al vectorilor j pentru a selecta anumiți vectori, care componente formează o unitate matrice E.
Dacă nu există astfel de vectori este posibil să se utilizeze una dintre următoarele moduri:
1. Efectuarea m schema de transformare Jordan - sistem de constrângere Gaussian (4.3), pentru a permite oricărei variabile în raport cu m. Rezultatul este un sistem de matrice (4.3) m bază vector - coloana j. și anume Vectori în care o coordonată este egal cu 1, iar celălalt - la zero, în cazul în care unitățile sunt în rânduri diferite ale matricei. Variabilele de bază corespunzătoare înregistrate în bazele de coloană ale primului tabel simplex.
2. Dacă sistemul original conține problema restricții LP inegalității cu semnul £, atunci introducerea variabilelor non-suplimentare negative pentru transformarea inegalităților în ecuație, obținem imediat acei vectori de bază, care stau la baza primului tabel simplex.
3. În cazul în care există semne de restricții în sistemul original al inegalităților ³, variabilele bilanț sunt introduse în partea stângă, cu semnul „-“. Vectorul corespunzător - coloana acestei variabile va avea următoarele coordonate:
În acest caz, vectorii vor fi pierdute, a cărui localizare se poate forma matricea unității E a primei baze. În fiecare astfel de inegalitate, împreună cu balanța variabilei introduse o altă variabilă (artificial): X # 945; 1. X # 945; 2.
Aceste variabile, de asemenea, a impus o cerință nu este negativă: X # 945; 1 ³ 0, X # 945; 2 ³ 0.
Funcția obiectiv în acest caz, se introduce un termen suplimentar de forma: ± M (. X # 945; 1 # 945 + X 2 + X + # 945; m), unde simbolul "+" este folosit în problema de minimizare (F®min) "-" semn în maximizarea (F®max). M ³0 - un număr foarte mare. Calculele de calculator iau, de obicei, M = 10 al 17-lea.
O metodă de rezolvare a acestei probleme se numește simplex - prin utilizarea de baze artificiale (sarcini extinse). tabelele Simplex sunt completate, la fel ca în simplex obișnuit - metoda. Aserțiunea: în cazul în care soluția de referință (planul de bază) este cel mai bun, toate variabilele artificiale sunt zero:
secvența de calcul a metodei simplex, luați în considerare exemplul următor.
Compania dispune de resurse de materii prime, echipamente și forța de muncă necesare pentru producerea de oricare dintre cele patru tipuri de bunuri comercializabile.
sarcini de informare Context
Tipul de produs Tipul de resursă
Costurile cunoscute de resurse pe unitatea de producție a fiecărui tip de bunuri, resurse, rezerve și profitul obținute de o întreprindere per unitate (Tabel. 4.1.).
Pentru a determina intervalul optim de produse, maximizarea profitului și evaluarea tuturor celor patru tipuri de resurse în ceea ce privește intervalul optim.
Noi introducem x1 variabile. x2. x3. x4. - respectiv, numărul de bunuri fabricate de tip A, B, C, D, apoi un model matematic poate fi scrisă ca
Pentru a rezolva problema simplex - metoda transformă inegalitatea în ecuație, obținem:
Conform conținutului economic al x5 variabile. x6. X7. X8 reprezintă suma neutilizată a cotei corespunzătoare fiecărui tip, astfel încât funcția obiectivă a acestor variabile suplimentare sunt incluse cu coeficienți zero.
tabelul simplex Primul se completează după cum urmează:
1. În rândul de sus al tabelului scrie coeficienții variabilelor necunoscute ale funcției obiectiv a problemei inițiale.
2. 1. 2. n coloane evacuate coeficienții x1 variabile. x2. xn în ecuațiile sistemului de constrângeri.
3. Coloana se înregistrează laturile drepte de ecuații limitări.
4. În bazele coloanelor sunt introduse acei vectori ale căror coordonate formează matricea E unitate (bază.).
5. Bazele de coloană se introduc coeficienții variabilelor de bază ale funcției obiectiv.
6. Rândul de jos al mesei ZJ - Cj = jbaz # 8729; j - Cj se numește șirul index sau numărul liniei și este utilizat pentru a testa obținute în următoarele soluții de masă pentru optimalitate.
tabel simplex Fore - un prim program de sprijin al problemei:
Aceasta corespunde faptului că nimic nu se face, resursele nu sunt utilizate, profitul - funcția obiectiv este zero și nu principalele variabile sunt limitele sale. Din punct de vedere geometric coordonatele vârful poliedrului obținut (0, 0, 0, 0, 360, 400, 134, 96).
Soluția de rezolvare a problemei este introducerea progresivă a unui plan de variabile cheie, câte unul pentru fiecare etapă a calculului, până la o soluție optimă.
Acesta este determinat în primul rând, care dintre cele patru variabile introduse în baza. Având în vedere că problema este rezolvată la maximum, este mai bine să înceapă cu un produs mai profitabil. Elementele cele mai profitabile într-un număr (50), în linia simplex indicelui de masă corespunde este mai mare în mărime absolută.
Definiți cât de mult este furnizată în eliberarea mărfurilor, depinde de resursele și standardele costurilor lor. 1 prime 180 suficient formă de unități B (360 kg. 2 kg). 2 tipuri de materii prime - cu 20 de unități de produse B (400. 20). timp suficient pentru a finanța echipamentul 16 (134) 8 unități de muncă - 8 (96. 12) unităților B. Este evident faptul că mai mult de 8 unități de mărfuri în care nu vor fi în stare să facă. Prin urmare, x3 variabilă în termeni egal cu 8 și se introduce în locul x8 variabilă. care este îndepărtat de la bază și devine zero. Sublinierea numărul 12, situat la intersecția coloanei 3 variabile de intrare și de ieșire x3 siruri de variabile x8.
Acest număr se numește rezolvarea cheie, elementul de ghidare.
Luați în considerare o a doua etapă de calcul tabelul 4. 2. Mai întâi, calculat variabila de intrare linie, notate în tabelul săgeată. Această linie se obține de la linia de start x8 întruchiparea prin împărțirea tuturor elementelor de pe elementul de ghidare, deoarece în această privință (1. 12), x3 variabilă înlocuiește x8 variabilă. Profitul baze de coloane, aplicată pe unitatea B (50).
După calcularea x3 linia recalculat coloanei de resurse.
Materii prime 1 specie scade, inițial a fost de 360 kg pe bunuri consumate unitatea de alimentare în 2 kg. toate produse (96. 12) a unităților în 8, prin urmare, rămâne neutilizată formă hrană 1 să fie 344 kg, adică 360 - 96/12 # 8729; 2 = 344.
In mod similar: 400 - 96/12 # 8729; 20 = 240 kg - 2 formă neutilizată brută, 134 - 96/12 # 8729; 8 = 70 Mașini - h - nefolosit echipamente rămase fundație ..
După coloană traduse resursele de coloane rămase simplex tabel.
Schema de conversie (de regulă Iordania - Gauss)
j - coloana coloană S-
Elementul Aij după conversie de regula Iordan - convertit în Gauss a'ij elementul. în cazul în care.
În acest caz, toate elementele care permit coloanei sunt zero, cu excepția elementului de separare, care devine egal cu unitatea.
Soluția metodei problemei simplex
Elementele din linia de index pot fi numărate, fie direct prin formula jbaz # 8729; j - Cj. sau regula Iordan - Gauss. Una dintre regulile care urmează să fie utilizate pentru calcularea, iar celălalt - ca un control. Rezultatul este al doilea program de sprijin: x1 = 0, x2 = 0, x3 = 8 x 4 = 0, x5 = 344 x 6 = 240, x7 = 70 x 8 = 0 și valoarea profiturilor - 400 d u. Din punct de vedere geometric, pentru a face trecerea la partea de sus a poliedrului cu coordonatele (0,0,8,0,344,240,70,0). Apoi, trebuie să verificați planul de optimalitate. Pentru această linie indicele vizibil și, în cazul în care conține elemente negative, planul poate fi îmbunătățit. După cum puteți vedea, acesta conține două numere negative, care indică faptul că profiturile pot fi crescută prin introducerea în baza x1 variabile sau x4. x4 Variabila este introdusă în baza, deoarece corespunde cu cea mai mare valoare absolută a numărului negativ - 27,5.
Dacă linia de index definit coloana cheie j. în care toate elementele sunt negative, problema LP nu are nici o soluție.
După construcția următoarei faze 3 linia de indicele de masă simplex include numai zerouri și numere pozitive. Acest lucru înseamnă că al treilea plan nu poate fi îmbunătățit și este cel mai bun:
x1 = 0, x2 = 0, x3 = 6,25, 7 = x4, x5 = 319.5, x6 = 65, x7 = 0, X8 = 0; în aceste condiții, producția nu poate fi obținut profituri de peste 592.5 g. unități. Astfel, eliberarea de bunuri este de 6,25 unități 7 r- și bunurilor unități ale reziduurilor materiei prime de primul tip și 319,5 kg de al doilea tip - 65 kg.