Metoda simplex pentru rezolvarea problemelor de optimizare a programării liniare, The BSEU economie - un blog

Metoda Simplex - o procedură de calcul bazat pe principiul îmbunătățirii continue a face trecerea de la un punct de referință (soluție de bază) la altul. Valoarea funcției obiectiv este îmbunătățită.

Soluția de referință este una dintre soluțiile fezabile, care sunt la nodurile regiunii fezabile. Verificarea pentru top optimă a nodurilor, ajunge la optim dorit. Acest principiu se bazează pe metoda simplex.

Simplex - un poligon convex în spațiu n-dimensional, cu n + 1 noduri care nu se află într-un singur hiperplan (hiperplan împarte spațiul în două jumătate).

De exemplu, linia împarte constrângerile bugetare cu privire la beneficiile disponibile și nu este disponibilă.

Este dovedit faptul că, dacă există soluția optimă, în mod necesar va fi găsit într-un număr finit de iterații (pași), cu excepția „buclă“.

Algoritmul simplex este format din mai multe etape.

Prima etapă. Construit modelul de optimizare original. Condiții suplimentare matrice originală este transformată într-o formă canonică redusă, care, printre toate celelalte forme canonice disting prin faptul că:

a) cea din dreapta a condițiilor (liber termeni bi) sunt valori non-negative;

b) condițiile sunt ele însele egalități;

c) cuprinde o matrice de condiții submatrice identitate completă.

În cazul în care termenii liberi sunt negative, atunci ambele părți ale inegalității sunt multiplicate cu - 1, iar inegalitatea este inversată. Pentru a converti inegalitățile în egalitati sunt introduse variabile suplimentare, care reprezintă în mod tipic cantitatea de resurse neutilizate. In aceasta, ele au un sens economic.

În cele din urmă, dacă adăugați variabile suplimentare, condițiile de matrice nu conține submatricea identitate completă, apoi a intrat variabilele artificiale care nu au nici un sens economic. Ele sunt introduse numai în scopul de a obține submatricea identitatea și să înceapă procesul de rezolvare a problemei folosind metoda simplex.

Soluția optimă a tuturor variabilelor artificiale (SP) trebuie să fie zero. Pentru aceste variabile artificiale sunt introduse în funcția țintă a problemei cu coeficienți mari negativi (-M) în rezolvarea problemei la maxim, și coeficienții pozitivi mari (M +), atunci când problema este rezolvată în min. În acest caz, chiar și o valoare variabilă artificială mică non-zero, va reduce drastic (creștere) valoarea funcției obiectiv. De obicei, de 1.000 de ori M trebuie să fie mai mare decât valoarea coeficienților variabilelor de bază.

Cea de a doua etapă. Construit inițial tabelul simplex și a căutat o anumită soluție inițială de bază. Un număr de variabile care alcătuiesc un sub-matrice unitară este luată ca soluția inițială de bază. Valorile acestor variabile sunt libere membrilor. Toate celelalte variabile extrabasis sunt egale cu zero.

A treia etapă. Verificarea soluției de bază pentru optimalitate se realizează cu ajutorul unor coeficienți speciali ai evaluărilor funcției obiectiv. În cazul în care toți coeficienții estimați ai funcției obiectiv sunt negative sau, atunci soluția de bază existentă la zero - optimă. În cazul în care cel puțin o estimare a coeficientului funcției obiectiv este mai mare decât zero, soluția de bază existentă nu este optimă și ar trebui să fie îmbunătățite.

A patra etapă. Trecerea la noua soluție de bază. Este evident că, în planul optim ar trebui să fie pus în aplicare, astfel încât variabilă crește funcția obiectiv în cea mai mare măsură. În rezolvarea problemelor pe profiturile planului optim introdus produse, a căror producție este cea mai profitabilă. Acest lucru este determinat de valoarea maximă pozitivă a obiectivului estimărilor coeficientului funcției.

tabelul simplex Coloana cu acest număr la o anumită iterație se numește o coloană generală.

Mai mult, în cazul în care cel puțin un element al coloanei generale aij0 strict pozitiv, apoi a căutat o linie generală (altfel sarcina nu este o soluție optimă).

Pentru a găsi linia generală toți membrii liberi (resurse) sunt împărțite în coloana generală elementele respective (rata de consum de resurse pe unitatea de produs). Din aceste rezultate este selectat cel mai mic. Rândul corespunzător în această iterație se numește general. Aceasta corespunde resursei, care limitează producția unei anumite iterație.

Element tabel simplex, situat la intersecția coloanei și rândul general, numit element de general.

Apoi, toate elementele liniei generale (inclusiv termenul constant) sunt împărțite în elementul general. Ca urmare a acestei operațiuni, elementul general, devine egal cu unu. În plus, este necesar ca toate celelalte elemente ale coloanei generale ar deveni egal cu zero, adică coloana generală ar trebui să fie unic. Toate liniile (cu excepția generală) sunt transformate după cum urmează. Elementele obținute ale noilor linii sunt multiplicate cu elementul corespunzător al coloanei de master și produsul se scade din elementele liniei vechi.

Noi valori ale variabilelor de bază pentru obținerea celulelor relevante într-o coloană de termeni liberi.

A cincea etapă. Soluția de bază rezultată este testat pentru optimalitate (vezi. Al treilea pas). Dacă este optimă, atunci calculele sunt terminate. În caz contrar, aveți nevoie pentru a găsi o soluție nouă bază (etapa patru), și așa mai departe. D.

Exemplu de rezolvare a problemelor de optimizare a metodei simplex de programare liniară

Să presupunem că avem nevoie pentru a găsi un plan optim de producție a două tipuri de produse (x1 și x2).