Etapa 1. Să dăm problema inițială a programării liniare formei canonice. Cu toate acestea, de la cerințele de bază la forma canonică a problemei de programare liniară se înregistrează constrângerile funcționale ale problemei sub forma unui sistem de ecuații liniare prin fețele drepte nonnegative. Această cerință rezultă din metoda Jordan-Gauss de determinare a soluției de bază a unui sistem de ecuații liniare. Condiția ca fețele drepte să nu fie negative este necesară pentru ca soluția de bază să fie admisibilă (suport).
Forma canonică a acestei probleme se obține prin introducerea unor variabile non-negative suplimentare (de bază sau echilibrate):
În sistem (3.6), x3. x4. x5 și x6 sunt variabile de bază sau echilibrate care transformă inegalitățile în egalități. Puteți da următoarea interpretare economică a variabilelor de bază. De exemplu, variabila x3 ≥ 0 adică dacă resursa "lapte" este folosită complet, atunci x3 = 0; dacă nu complet, atunci x3> 0. Astfel, x3 este excesul de resurse "lapte". În mod similar, variabilele de bază rămase pot fi interpretate.
Pasul 2. Elaborarea primului plan de bază
Completăm primul pas al mesei simplex
În coloanele 1-7 și liniile 1-5 se scriu coeficienți pentru necunoscuți și termeni liberi ai sistemului (3.6). În coloana variabilelor de bază le notăm notația. De la începutul soluției de estimare a variabilelor de bază ale celor necunoscute le dăm valori egale cu zero. Estimările variabilelor libere (cantitatea de ieșire) sunt luate egale cu valorile lor în funcția obiectivă. Soluția problemei de programare liniară în tabelul simplex este în coloana termenilor liberi, adică soluția din prima etapă arată ca:
Coloana de control servește pentru a verifica corectitudinea soluției și este produsul coeficienților coloanei termenilor liberi prin estimările variabilelor corespunzătoare. Suma acestor produse dă valoarea funcției obiective, în acest caz F (x) = 0
Pasul 3. Verificarea planului de optimitate
Un semn al optimalității soluției problemei este absența valorilor pozitive în linia funcției obiective. În cazul nostru, această condiție nu este îndeplinită (există două numere pozitive - 16 și 14). Prin urmare, planul nu este optim și soluția trebuie continuată.
Pasul 4. Determinați coloana și rândul de conducere
Din prima versiune a planului, în care nu lansăm nimic, ne îndreptăm spre a doua opțiune. Tranziția este următoarea: se definește coloana de conducere și rândul (uneori este folosit termenul "rezolvare") și elementul de conducere.
Dacă te uiți la linia de funcția obiectiv al primei iterație (linia 5), există două numere pozitive -16 și 14, care sunt coeficienții funcției obiectiv, și reprezintă prețurile produselor fabricate (c1 = 16 -Contravaloarea prețul de înghețată; c2 = 14 - prețul ciocolatei înghețată), care este, în a doua etapă putem introduce în plan, sau eliberarea de înghețată cremoasă sau de ciocolată. Puteți introduce un plan pentru producția de înghețată cremă, deoarece duce la o creștere mare a venitului (16> 14). Coloana corespunzătoare acestei cifre (16) se numește comandă.
Din punct de vedere matematic, alegerea coloanei de conducere se face conform regulii: coloana de conducere este j>
După selectarea coloanei de conducere, treceți la selectarea liniei de conducere. Pentru aceasta, coeficienții din coloana termenilor liberi sunt împărțiți prin coeficienții corespunzători ai coloanei de conducere:
= 100, iar printre ele se selectează valoarea minimă (100). Linia corespunzătoare acestui minim va conduce.
De ce este selectată valoarea minimă? Faptul este că coeficienții din coloanele 1-6 și rândurile 1-4 ale tabelului simplex reprezintă consumul de resurse pe unitate de ieșire, iar coloana 7 este disponibilitatea acestor resurse. Aceasta este relația, de exemplu 400 / 0.8 = 500. înseamnă că resursa "lapte", putem emite 500 kg. crema de înghețată, dar în acest caz, egalitatea 3 la sistem (3.6) nu va fi îndeplinită, deoarece x5 ≥0 Astfel, putem produce numai 100 kg. cremă și această linie (3) devine cea mai importantă.
Din punct de vedere matematic, alegerea liniei de conducere se face conform regulii: linia de conducere → min>, unde a b ij sunt coeficienții coloanei de conducere.
Uneori, când selectați linia de conducere, obțineți oarecum egal. Acest lucru poate complica vectorul liniei de conducere și poate duce la o buclă.
În astfel de cazuri, metoda Kreko este utilizată pentru a selecta linia de conducere, care este după cum urmează. Elementele de șiruri care au aceleași valori cele mai scăzute. sunt împărțite în elemente de rezolvare prospective, iar rezultatele sunt introduse în linii suplimentare. Pentru linia de conducere se alege cel în care să se întâlnească cel mai mic privat atunci când se citește masa de la stânga la dreapta de către coloane.
Trimiteți-le prietenilor: