Scopul serviciului. Calculatorul online este conceput pentru a rezolva probleme de programare liniară prin metoda simplex prin trecerea la KPLP și NWP. În acest caz, problema minimizării funcției obiectiv este redusă la problema de a găsi maximul prin transformarea funcției obiectiv F * (X) = -F (X). Este, de asemenea, posibilă realizarea unei sarcini duale.
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.
Trecerea de la problema minimizării funcției obiectiv la problema de maximizare
Problema minimizării funcției F (X) poate fi ușor redusă la problema maximizării funcției F * (X) sub aceleași restricții prin introducerea funcției: F * (X) = -F (X). Ambele probleme au aceeași soluție X *, iar aici min (F (X)) = -max (F * (X)).
Să ilustrăm acest fapt grafic:
Pentru a optimiza funcția țintă, folosim următoarele concepte și metode.
Un plan de referință este un plan cu cele definite prin variabile de bază libere.
Un plan de bază este un plan de bază cu variabile de bază zero.
Planul optim este un plan de bază care satisface funcția obiectivului optim (FC).
Elementul de conducere (rezolvare) este coeficientul liberului necunoscut, care devine baza, iar coeficientul însuși este convertit în unitate.
Linia de ghidare este linia elementului de conducere, în care se exclude baza necunoscută cu coeficientul unității, care este exclusă în timpul transformării (linia cu coeficientul minim de limită, vezi mai jos).
Coloana de ghidare este coloana elementului principal, a cărui liberă necunoscută este tradusă în baza (coloana cu beneficiul maxim, vezi mai jos).
Variabilele x1. ..., xm. care apar cu coeficienții unității doar într-o singură ecuație a sistemului, cu zero în rest, se numesc de bază sau dependenți. În sistemul canonic, exact o variabilă de bază corespunde fiecărei ecuații. Tranziția se realizează utilizând metoda Gauss-Jordan. Ideea principală a acestei metode este de a reduce sistemul de m ecuații cu n necunoscute în forma canonică prin intermediul operațiilor elementare pe rânduri.
Variabilele n-m rămase (xm + 1, ..., xn) sunt numite variabile independente sau independente.
Soluția de bază se numește soluție de bază admisibilă. dacă valorile variabilelor de bază xj ≥0, care este echivalentă cu condiția de non-negativitate bj ≥0.
O soluție de bază admisibilă este un punct unghiular al unui set admisibil S al unei probleme de programare liniară și este denumit uneori un program de sprijin.
Dacă între numerele non-negative bj sunt egale cu zero, atunci soluția de bază admisibilă se numește degenerat (punctul unghiular degenerat) și problema corespunzătoare a programării liniare se numește degenerare.
Exemplul №1. Reduceți problema de programare liniară la un standard LPA.
F (X) = x1 + 2x2 - 2x3 → min cu constrângeri:
4x1 + 3x2 - x3 ≤10
- 2x2 + 5x3 ≥3
x1 + 2x3 = 9
Pentru a reduce APL în forma canonică, este necesar:
1. Modificați semnul funcției obiectiv. Reducem problema F (X) → min la problema F (X) → max. Pentru a face acest lucru, multiplicați F (X) cu (-1). În prima inegalitate a sensului (≤) se introduce variabila de bază x4; în cea de-a doua inegalitate de semnificație (≥), introducem variabila de bază x5 cu un semn minus.
4x1 + 3x2 -1x3 + 1x4 + 0x5 = 10
0x1 -2x2 + 5x3 + 0x4 -1x5 = 3
1x1 + 0x2 + 2x3 + 0x4 + 0x5 = 9
F (X) = - x1 - 2x2 + 2x3
Tranziția la NWFP.
Matricea extinsă a sistemului de constrângeri - egalități ale acestei probleme:
Articole similare
-
Rezolvarea problemelor de programare liniară cu programul Excel
-
Soluția de sarcini tipice - compuși organici care conțin oxigen - chimie organică - indemnizație
Trimiteți-le prietenilor: