Forma canonică a LPP este o problemă de programare liniară a formei ax = b unde a este matricea coeficientului și b este vectorul de constrângere.
Instrucțiuni. Selectați numărul de variabile și numărul de rânduri (numărul constrângerilor). Soluția rezultată este salvată într-un fișier Word.
Modelul matematic al unui ZLP este numit de bază. dacă constrângerile în ea sunt reprezentate sub formă de ecuații, cu condiția ca variabilele să nu fie negative.
Modelul matematic se numește canonic. dacă sistemul său de constrângere este reprezentat ca un sistem de ecuații linear independent (rangul sistemului r = m), în sistem este alocată o singură bază. variabilele libere sunt definite și funcția obiectivă este exprimată în termeni de variabile libere. Liniile drepte ale ecuațiilor nu sunt negative (bi ≥ 0).
Variabilele care intră într-una din ecuațiile unui sistem cu un coeficient unu și sunt absente în alte ecuații sunt numite necunoscute de bază. și toți ceilalți sunt liberi.
Soluția sistemului este numită soluția de bază. dacă variabilele libere din ea sunt 0 și are forma:
Xbas = (0, 0; b1 ..., bm), f (Xba3) = c0
Soluția de bază este punctul de colț al setului de soluții ale sistemului, adică determină vârful poligonului de decizie model. Printre aceste soluții se numără faptul că funcția obiectivă are o valoare optimă.
O soluție de bază este numită soluție de sprijin dacă este admisibilă, adică toate laturile drepte ale ecuațiilor sistemului (sau inegalitățile) sunt pozitive bi ≥ 0.
Forma compactă a modelului canonic are forma:
AX = b
X ≥ 0
Z = CX (max)
Conceptul de soluție admisibilă, domeniul soluțiilor admisibile, soluția optimă a problemei de programare liniară.
Definiție 1. Un vector X care satisface sistemul constrângerilor APL, inclusiv condițiile de non-negativitate, dacă este cazul, se numește o soluție admisibilă a APL.
Definiție 2. Colectarea tuturor soluțiilor admisibile formează domeniul soluțiilor admise (ODT) 3L.
Definiție 3. O soluție fezabilă pentru care funcția obiectivă atinge un maxim (sau minim) este numită soluția optimă.
Exemplul №1. Următoarea problemă LP poate fi redusă la forma canonică: F (X) = 5x1 + 3x2 → max sub constrângeri:
2x1 + 3x2 ≤20
3x1 + x2 ≤15
4x1 ≤16
3x2 ≤12
Modelul este scris în formă standard. Să introducem variabilele non-negative x3. x4. x5. x6. pe care le adăugăm la partea stângă a constrângerilor de inegalitate. În funcția obiectiv, introducem toate variabilele suplimentare cu coeficienți egali cu zero:
În prima inegalitate a sensului (≤) introducem variabila de bază x3. În cea de-a doua inegalitate a sensului (≤) se introduce variabila de bază x4. În a treia inegalitate, introducem variabila de bază x5. În a 4-a inegalitate, variabila de bază x6. Obținem forma canonică a modelului:
2x1 + 3x2 + 1x3 + 0x4 + 0x5 + 0x6 = 20
3x1 + 1x2 + 0x3 + 1x4 + 0x5 + 0x6 = 15
4x1 + 0x2 + 0x3 + 0x4 + 1x5 + 0x6 = 16
0x1 + 3x2 + 0x3 + 0x4 + 0x5 + 1x6 = 12
F (X) = 5x1 + 3x2 + 0x3 + 0x4 + 0x5 + 0x6 → max
Trimiteți-le prietenilor: