Metoda simplex de optimizare liniară a explicat simplu

Modelarea programelor liniare

La modelarea programelor liniare, diverși parametri precum B. Se pot determina timpii de prelucrare a pieselor sau a capacităților mașinii. Apoi este definită o funcție obiectivă, care urmează să fie maximizată sub anumite constrângeri. Funcția obiectivă este adesea funcția de profit, deoarece maximizarea profitului net este un obiectiv cheie pentru companii. Constrângerile sunt descrise de lipsa resurselor (de ex. B. Capacitate, timp, spațiu). Apoi puteți rezolva problema folosind metoda simplex.

• Puteți învăța cu ușurință procedura de creare a modelelor liniare dacă vă faceți un exemplu simplu: Să presupunem că aveți trei mașini M₁, M₂ si m₃ pe care cele două produse P₁ și P₂ ar trebui să fie produs. Mașinile au capacități diferite și este nevoie de timp pentru a prelucra un anumit produs pe mașini pentru perioade diferite de timp, iar produsele finale finite generează profituri diferite departe.
  instagram viewer
• Acum căutăm programul de producție cu profit maxim, adică programul de producție în care se obține cel mai mare profit.

Exemplu cu valori numerice și introducere în metoda simplex

În pasul următor aveți nevoie de valori numerice concrete pentru a vă modela problema. Să presupunem că pentru editarea P₁ pe M₁ 2 ore se acumulează pe M₂ 3 ore și pe M₃ 4 ore. Pentru P₂ cad pe M₁ 4 ore pe, pe M₂ 5 ore și pe M₃ 3 ore. Capacitățile mașinii pentru M₁ 500 de ore, pentru M₂ 300 de ore și pentru M3 600 de ore. Profiturile pentru produsele finite P₁ sunt 3 euro / bucată, pentru produsele finite P₂ 4 euro / buc.

1. Cel mai bine este să creați un tabel cu trei rânduri și trei coloane, cu spațiu suplimentar pentru titlurile rândurilor și coloanelor. Ar trebui să lase coloane. De exemplu, timpul de procesare al lui P se află în câmpul „Coloana 1 și Rândul 1”₁ pe M₁, în câmpul „Coloana 2 și Linia 3” timpul de procesare al lui P₂ pe M₃. Coloana 3 arată capacitățile mașinii celor trei mașini.


Algoritmul Gaussian al sistemelor liniare de ecuații explicat pe scurt

Veți întâlni sisteme liniare de ecuații pentru prima dată în gimnaziu pe ...

2. Acum aveți nevoie de două variabile x₁, X₂ definiți cantitățile de producție de P₁ și P₂ corespunde.
3. Deci obțineți constrângerile de 2x₁+ 4x₂ ≤ 500 (mașină 1), 3x₁+ 5x₂ ≤ 300 (mașină 2) și 4x₁+ 3x₂ ≤ 600 (mașina 3). În fiecare caz, există inegalități, deoarece capacitățile nu trebuie să fie complet epuizate.
4. Funcția obiectivă (profit) care trebuie maximizată este G (x₁, X₂) = 3x₁+ 4x₂ -> max.
5. În plus, condițiile de non-negativitate ale lui x se aplică cantității de producție₁, X₂ ≥ 0. Vedeți, toate ecuațiile sunt ecuații liniare. Dacă le priviți împreună, veți avea o problemă de optimizare liniară.

Optimizarea liniară și aplicarea metodei simplex

Ideea pentru rezolvarea unui program liniar este că inegalitățile sunt eliminate prin introducerea „variabilelor slack” în Ecuații iar problema de optimizare modificată este rezolvată ca LGS. Prin urmare, metoda simplex este foarte similară cu algoritmul Gaussian pentru rezolvarea LGS.

1. Exemplu: un avion este împărțit la trei mărfuri G₁, G₂, G₃ să fie încărcat cu cea mai mare valoare totală posibilă de transport. Acestea au un spațiu necesar de 1, 0,2 sau 6 dm³, au o greutate de 1, 0, 4 și 8 kg și o valoare de 10, 3 sau 50 Euro. Cum se încarcă ideal aeronava când spațiul de încărcare este de 2000 dm³ și poate transporta maximum 3000 kg de marfă?
2. Tu definesti x₁, X₂, X₃ ca cantități de mărfuri G₁, G₂, G₃.
3. Acum puteți configura constrângerile cu variabile slack după cum urmează: x₁+ 0,4x₂+ 8x₃+ x₄ = 3000 și x₁+ 0,2x₂+ 6x₃+ x₅ = 2000. Funcția obiectivă (valoarea totală a transportului) este G (x₁, X₂, X₃) = 10x₁+ 3x₂+ 50x₃ -> max. Puteți schimba acest lucru aducând toate variabilele pe o singură pagină (G-10x₁-3x₂-50x₃ = 0).
4. Apoi configurați panoul Simplex. Are 3 rânduri și 7 coloane. În partea stângă introduceți x în coloane₁, X₂, X₃, X₄, X₅ și G ca titluri. În dreapta, b este singura coloană. Aici sunt enumerate cantitățile optime de mărfuri și cea mai mare valoare totală de transport posibil. A treia linie este linia țintă. (Control: în cele trei linii cu titlurile menționate mai sus sunt numerele: Linia 1: 1, 0,4, 8, 1, 0, 0, 3000, Linia 2: 1, 0,2 6, 0, 1, 0, 2000 și Linia 3: -10, -3, -50, 0, 0, 1, 0).
5. Acum procedați ca atunci când utilizați metoda Gaussiană pentru a rezolva un LGS. În primul pas schimbați linia 1 resp. Linia 2 este trimisă și adăugată la cealaltă linie astfel încât să apară doar 1 în „Linia 1 + Coloana 1” și un 0 în „Linia 2 + Coloana 1”. Ca urmare, valorile din linia țintă se modifică și ele automat.
6. În acest caz, de exemplu, puteți înmulți rândul 2 cu -1 și îl puteți adăuga la rândul 1 și înmulți rândul 2 cu 10 și adăugați la linia 3 (control: linia 1: 0, 0,2, 2, 1, -1, 0, 1000, linia 2: rămâne aceeași, linia 3: 0, -1, 10, 0, 10, 1, 20.000).
7. În al doilea pas, luați coloana 2 și creați un 0 transformând „Rândul 2 + Coloana 2” și apoi un 1 în „Rândul 1 și Coloana 2”. Din nou, trebuie remarcat modul în care se modifică linia țintă.
8. Pașii de transformare ar fi, de exemplu, să multiplicați rândul 1 cu -1 și să adăugați la rândul 2 și rândul 1 la 5 și să adăugați la rândul 3 (Verificați: după efectuarea ambilor pași, rezultatul este: linia 1: 0, 1, 10, 5, -5, 0, 5000, linia 2: 1, 0, 4, -1, 2, 0, 1000 și linia 3: 0, 0, 20, 5, 5, 1, 25.000).
9. Acum puteți citi soluțiile din partea dreaptă a panoului. Acest lucru are ca rezultat o valoare totală a transportului de 25.000 de euro, 5000 de unități de bun 1, 1000 de unități de bun 2 și nu sunt transportate nicio unitate de bun 3.

Vă rugăm să rețineți că soluția tabloului simplex are ca rezultat o soluție optimă numai dacă sunt afișate numai rezultate pozitive în linia țintă din stânga după ultimul pas de remodelare. Socoteală stand. Ați interiorizat sistemul după alte 2-3 exemple și veți putea rezolva astfel de sarcini în viitor într-un mod ludic.