Să considerăm un simplex metodă de rezolvare a programării liniare (LP). Ea se bazează pe trecerea de la un plan de suport la altul, în care obiectivul valoare funcției crește.
Algoritmul simplex metoda este următoarea:
- Sarcina inițială este tradus într-o formă canonică prin introducerea unor variabile suplimentare. variabile suplimentare sunt introduse cu semnul (+), în cazul în care aceeași specie ≥ apoi semnat pentru inegalitatea formei ≤ (-). Funcția țintă de variabile suplimentare introduse cu mărcile respective cu un factor de 0. deoarece funcția obiectiv nu ar trebui să fie în același timp, schimba sensul său economic.
Pi scrise din vectorul coeficienților variabilelor și o coloană de termeni liberi. Această acțiune este determinată de numărul de vectori de unități. Regula - vectorii unitate ar trebui să fie la fel de mult ca și inegalitățile în sistemul de constrângeri.
Ulterior, datele originale de intrare este de la masa simplex. Versorii bază sunt făcute, și excluderea lor din baza, găsiți soluția optimă. Coeficienții funcției obiectiv este scris cu semnul opus.
testul Optimalitate pentru probleme LP - soluție optimă, în cazul în care f -Row toți coeficienții sunt pozitive. Regula pentru a găsi coloana de autorizare - se poate observa f - linia și cel mai mic este ales dintre elementele sale negative. vector Pi conține devine permisivă. Regula care permite alegerea elementului - este un raport de elemente pozitive care permit coloana elementelor P0 vectorului și numărul care dă cel mai mic raport se fixează la elementele cu privire la care conversia tabelul simplex va fi generat. Un șir de caractere care conține elementul numit rezoluție linie. În cazul în care coloana nu este elemente pozitive permisive, problema nu are nici o soluție. După determinarea elementului de rezolvare a tranziției la traducerea noului simplex - tabel.
Cum de a completa un nou simplex - tabel. În loc să permită să aplice unității elementului și alte elemente considerate egale cu 0. Se permite vectorului introdus în baza regulii care corespunde vectorului de zero, iar restul vectorii de bază înregistrat neschimbate. Liniile de rezoluție Elementele împart un element permit și celelalte elemente convertite prin dreptunghiurile regulă.
Deci, atâta timp cât f - line a tuturor elementelor care nu vor fi pozitive.
Luați în considerare soluția problemei folosind algoritmul discutat mai sus.
având în vedere:
Aici este problema de a forma canonică:
Umple Simplex - tabel:
dreptunghiuri Regulă:
Recalculăm primul P0 element de vector. De ce alcătuiesc un dreptunghi de numere și de a obține :.
Calcule similare sunt efectuate pentru toate celelalte elemente ale simplex - tabel:
Obținut planul f - rândul cuprinde un element negativ - (-5/3) vectorul P1. Acesta conține în coloana sa, singurul element pozitiv, care va fi fixată la elementele. Asigurați-un tabel de conversie în ceea ce privește acest articol:
Absența elementelor negative în f - linia înseamnă că planul optim găsit:
F * = 36/5, X = (12/5, 14/5, 8, 0, 0).
Bibliografie recomandată
Soluție de programare liniară pentru a comanda
Comanda orice locuri de muncă în această disciplină poate fi pe site-ul nostru. Atașați fișiere și specificați intervalul de timp poate fi pe pagina de comandă.
articole similare
