Optimizarea problemelor de transport

Dobândirea de competențe pentru rezolvarea problemelor de transport utilizând echipa „caută soluții“ și potențialul metodei.

Modelul matematic al problemei de transport

Practic toate problemei programării liniare poate fi rezolvată folosind unele modificări ale metodei simplex. Cu toate acestea, există proceduri de calcul mai eficiente pentru rezolvarea unor tipuri de probleme de programare liniare, bazate pe constrângerile specifice ale acestor probleme. Luați în considerare așa-numita problemă de transport a costului criteriilor care pot fi rezumate după cum urmează.

Punctele de plecare t A1. A2. Am. în care un anumit număr de unități ale unui furnizori de produse omogene vor fi denumite în continuare, concentrate, notate ai (i = 1, 2 m). Acest produs este consumat n punctele B1. B2. Bn. care va fi numit consumator; Consumul de bj notat (j = 1, 2 n). Costurile cunoscute pentru transportul de unități de produs de la - Ai la punctul Bj. Sij care sunt egale și sunt prezentate în costurile de transport matricea C = (cij).

Este necesar pentru a face un astfel de plan consumatorilor atașați furnizorilor, adică Planul de transport, în care toate produsul este scos din puncte Aj la punctele Vj în funcție de necesități, iar suma totală a costurilor de transport va fi minim.

Notăm cantitatea de produs transportat de la un punct la altul Ai Bj. de hij. Toate variabilele xij. Pentru concizie. apoi funcția obiectiv a problemei va fi:

și restricțiile sunt după cum urmează:

Condiții (11) înseamnă satisfacerea deplină a cererii la toate punctele de consum; Condiții (12) definesc un export de produse de la toți furnizorii.

O condiție necesară și suficientă pentru problema (10) - (12) este o condiție echilibru:

Problema de transport, care are loc în ecuația (13), numita închis și poate fi rezolvată ca o problemă de programare liniară folosind metoda simplex.

Datorită particularităților variabilelor problemă și limitările sistemului dezvoltat o metode speciale, mai puțin greoaie de soluționare a acesteia. Metoda cea mai utilizată este metoda de potențiale la care fiecare linie i-lea (i-lea furnizor) este stabilit potențialul interfață de utilizare, care poate fi interpretat ca un preț produs în furnizor element, și fiecare j coloană (j-clienți) set potențial Vj, care pot fi luate de probă pentru consumatori punct de preț produs. În cel mai simplu caz prețul produsului în punctul de consum este egal cu furnizorul său punct de preț, plus costurile de transport pentru livrarea acestuia, și anume

Dacă soldul (13) nu este îndeplinită, atunci limita (11) sau (12) au forma unor inegalități, cum ar fi „mai mic sau egal cu“. Problema de transport, în acest caz, se numește deschisă. Pentru a rezolva problema de potențiale de transport deschise sa închis pentru a reduce problema prin introducerea sau utilizator fictive în cazul în care condiția inegalitate rândul său, (12) sau un furnizor fictiv - în cazul conversiei la restricțiile de inegalitate (11).

Luați în considerare etapele metodei de potențiale pentru o problemă de transport închis mai în detaliu. În primul rând trebuie menționat faptul că în condițiile de echilibru (13) rangul sistemului de ecuații liniare (11) și (12) este egal cu m + n - 1. Prin urmare dintr-un total de m bază x n necunoscute necunoscut este m + n - 1. În consecință, pentru orice distribuție de bază admisibilă în transportul matrice (tabelul ofertei) prezentată în formă generală în tabel. 6, se va angaja cu precizie m + n - 1 celule, care va fi numit de bază, spre deosebire de alte celule libere. celulă ocupată va marca o linie diagonală.

Tabelul 6 - transport Matrix

Etapa 1 .Pervonachalnoe asigurarea consumatorilor pentru furnizori. Luați în considerare două metode de obținere a distribuției inițiale (program de sprijin inițial): metoda nord-vest colț și metoda de cel mai mic cost. Fiecare dintre aceste metode în timpul umplerii unei celule, cu excepția ultimului rând este șters sau matricea de transport numai, sau numai coloana; numai atunci când se umple ultima celulă barat și linia și coloana. Această abordare va asigura că celula de bază va fi exact m + n - 1. Dacă la unele umplere (nu ultimul), celulele sunt satisfăcute simultan și furnizorul de energie și consumator, se elimină, de exemplu, doar o linie și o cușcă neocupate se completează în coloana respectivă, astfel numita „livrare de la zero“, iar apoi a lovit din coloană. Pentru a identifica celulele de obicei în paranteze indică numărul rândului și coloanei sale. În metoda din colțul de nord-vest este întotdeauna în primul rând, este umplut cu celule (printre Undelete), în picioare pe partea din stânga sus (nord-vest) colț al matricei de trafic. Exemplu de distribuție inițială prin această metodă este prezentată în Tabelul. 7: celulă umplută (1; 1) se elimină, iar prima coloană este umplută cu celule (1, 2) și primul rând se elimină; de celule umplute (2, 2) se elimină, iar coloana a doua; de celule umplute (2, 3), iar al doilea rând se elimină; de celule umplute (3, 3) și coloana a treia se elimină; In final, celula este umplută cu (3: 4) și a lovit ultimul rând și coloană. Numărul este m + n-1 celule ocupate = 3 + 4-1 = 6. Costul total al punerii în aplicare a planului de transport va fi:

Tabelul 7 - Exemplu de metodă de distribuție inițială colțul de nord-vest

Dezavantajul acestei metode este că ignoră valorile elementelor caracteristice ale costurilor de transport Sij matriceale, prin care obținute prin această metodă distribuția inițială (primul plan de transport de referință) poate fi suficient de departe de a fi optimă.

În diferite modificări ale metodei de costul cel mai mic de umplere a celulelor matricei de transport se realizează cu valorile cij cantităților. Deci, în modificarea „preferințe duble“ celule marca cu cel mai mic cost al primului transport al fiecărui rând și apoi fiecare coloană. Celulele au două mărci umplute mai întâi, apoi umple celulele cu un marker și o mulțime de date nealocată sunt înregistrate în celulele nemarcate cu costul cel mai mic. Astfel, două celule cu aceeași valoare a preferinței traficului de celule, prin care cantitatea mai mare de trafic. Eliminarea rândurilor și coloanelor se efectuează în conformitate cu regulile descrise mai sus pentru umplerea celulelor. EXEMPLU Metoda de distribuție inițială a cel mai scăzut cost pentru aceleași date de intrare ca și anterior prezentate în tabel. 8.

Tabelul 8 - Exemplu de distribuția inițială a valorilor de mai puțin

Procedura de umplere a celulelor (2, 1), (3, 2), (1, 3), (2, 4), (1, 4), (3, 4). Costul total al transportului, prezentate în tabelul. 3.7, sunt după cum urmează:

f (X) = 1 * 30 + 2 * 100 + 2 * 40 + 2 * 70 + 3 * 20 + 4 * 20 = 590.

Prin urmare, planul de transport este mult mai aproape de optim decât planul elaborat prin metoda din colțul de nord-vest.

Pasul 2: Verificați dacă planul de transport optim rezultat. Introducem indicatori special pentru fiecare interfață linie de transport al matricei (fiecare furnizor), unde i = 1, t, și indicatori Vj pentru fiecare coloană (fiecare utilizator), unde, j = 1, n. Aceste cifre sunt numite potențiale ale furnizorilor și consumatorilor, este convenabil să fie interpretat în sensul că prețul produsului în paragrafele relevante ale furnizorilor și consumatorilor. Potențialele sunt alese astfel încât celulele umplute pentru (i, j) satisfac ecuația (14). Setul de ecuații (14), compus din toate celulele umplute (toate bază necunoscute) formează un sistem de m + n - 1 ecuații liniare cu n necunoscute m + UI si vj. Acest sistem este compatibil întotdeauna, în care unul din valoarea necunoscută poate fi stabilită în mod arbitrar (de exemplu, u1 = 0), în timp ce valorile necunoscute rămase sunt în mod unic de sistem.

Să considerăm procesul de identificare a potențialului de baza distribuției inițiale prin metoda colțului de nord-vest, reprezentată în tabelul. 7. Prin setarea u1 = 0 și folosind formula (14) umplut cu celule (1, 1) și (1, 2), descoperim v1 = v2 = 4 și 5. Cunoașterea V2, prin celule umplute (2; 2) găsim u2 = 2, și știind u2. prin celula umpluți (2; 3) v3 = 8. găsim Știind v3, a coliviei completat (3; 3) descoperim u3 = 1, iar cușca apoi umplută (3; 4) descoperim v4 = 5. Rezultatele sunt prezentate în Tabelul. 9, în cazul în care potențialii furnizori sunt date în ultima coloană, iar potențialii consumatori - în ultimul rând.

Tabelul 9 - Determinarea potențialului bazei inițiale pentru metoda de distribuție colț nord-vest

Pentru a evalua alocarea optimă pentru toate celulele (i, j) matricea de trafic determinate prin evaluarea lor, care este notat cu dij, conform formulei:

Folosind interpretarea acceptată anterior, expresia poate fi interpretată ca suma prețul produsului de la furnizor, precum și costul de transport; prin scăderea această sumă este comparată cu prețul produsului la Vj consumatorului respectiv. Evident, evaluarea celulelor umplute sunt zero (prețul de consum acoperă costurile și furnizorul de transport). Astfel, o alocare optimă poate fi judecat de valoarea numărului de celule disponibile. În cazul în care evaluarea unei celule libere este negativ, acesta poate fi interpretat după cum urmează: prețul oferit de către consumatorul relevant, mai valoarea de cost al furnizorului și costul de transport, și anume în cazul în care celula a fost ocupată, ar fi posibil să se obțină beneficii economice suplimentare. În consecință, distribuția stării optimalitate este starea non-negativitate celulelor matricei devizelor de trafic gratuite.

Estimările de celule în conformitate cu formula (15) este convenabil reprezentată sub forma unei estimări ale matricei. Pentru distribuția considerată anterior obținută prin colțul de nord-vest (a se vedea tabelul 9 ..), numărul de celule de matrice este după cum urmează:

Prezența unui număr mai mare de evaluări negative ale celulelor libere sugerează că acest lucru este departe de planul optim de trafic (reamintească faptul că costul total al transportului planului sunt în 1170).

(. Tabelul 10) Pentru o distribuție a valorilor obținute prin cel puțin, numărul de celule de matrice este după cum urmează:

Din moment ce toate estimările sunt non-negativ, atunci nu este posibil să se îmbunătățească planul de transport, și anume este optim (costul total al transportului planului sunt 590). Mai mult, trebuie remarcat faptul că, în acest caz, evaluarea tuturor celulelor disponibile strict mai mare decât zero, adică, orice alt plan oferind locuri de muncă pentru cel puțin una dintre aceste celule va fi mai mică decât optimă. Acest lucru sugerează că a găsit planul optim este unic. Prezența la zero estimări ale celulelor libere în planul optim de transport, dimpotrivă, indică non-unicitatea planului optim.

Etapa 3. Consolidarea planului de transport suboptimal (cicluri de redistribuire). Pentru a îmbunătăți planul de transport suboptime, transport selectat matrice de celule cu o evaluare negativă; în cazul în care astfel de celule sunt puține, este de obicei (dar nu neapărat) selectat celula cu cea mai mare valoare absolută de evaluare negativă. De exemplu, pentru distribuția prezentată în tabelul. 9, o astfel de celulă poate fi celula (1, 3) (a se vedea estimări ale matricei (16).).

curba închisă este construită pentru celula selectată (circuit), vârful inițial, care se află într-o celulă selectată în timp ce toate celelalte vârfuri sunt ocupate de celule; în care direcțiile de lungimi de buclă individuale pot fi orizontale și verticale numai. Circuit Vertex cu excepția primului, este ocupat de o celulă, în care segmentele de linie de contur formează un colț (nu poate fi văzută ca nodurile, unde segmentele de contur orizontale și verticale se intersectează). Evident, numărul de segmente de contur, ca nodurile sale, este chiar. Vârfurile circuitului sunt aranjate alternativ semne „+“ și „-“ începând cu semnul „+“ în celulă liberă selectată. Un circuit simplu este prezentat în fantomă în tabelul. 9, deși forma de circuit poate fi destul de variate (de exemplu, conturul în tabel. 12).

Cantitatea redistribuite de livrare definită ca cea mai mică dintre valorile din nodurile de circuit de alimentare cu semnul „-“, iar această valoare crește livrarea la nodurile cu semnul „+“ si scaderea livrarea la nodurile cu semnul „-“. Această regulă se asigură că circuitul nu va topuri de aprovizionare negativ, celula aleasă inițial este ocupat, în timp ce una din celulele folosite în acest caz, în mod necesar liber. În cazul în care valoarea ofertei redistribuite este furnizarea de nu una, ci mai multe vârfuri de contur cu semnul „-“ (este nevoie doar loc în realocarea circuitului în tabelul 9.), care a lansat doar o singură celulă, de obicei, cu cel mai mare cost de transport, precum și toate celelalte astfel de celule sunt ocupate cu livrare la zero.

Rezultatul acestor operații pentru Tabelului prezentate. 9 de distribuție de alimentare este prezentată în Tabelul. 11. Costul total al transportului pe acest plan

f (X) = 4 * 30 + 5 * 0 + 2 * 30 + 3 * 100 + 7 * 10 + 4 * 110 = 990, care este semnificativ mai mică decât sumele anterioare de cost 1170, cu toate că traficul în planul Table. 11 nu este încă optimă. Acest lucru este evidențiat prin prezența valori negative în celulele matrice ale modificărilor planului (corespunzător potențialele vj ui și a găsit metoda prezentată în descrierea din etapa 2):

Tabelul 11 ​​- Rezultatele problemei transportului prin rezolvarea capabilităților la baza distribuției inițiale prin metoda colțului de nord-vest

Probleme de transport, în condițiile de bază ale traficului, care se produc celule angajate cu livrare zero (sau în alocarea inițială, sau în procesul de iterații) sunt numite degenerate; un exemplu al acestei probleme este prezentată în Tabelul. 11. În cazul degenerată există riscul de probleme de transport în buclă, adică repetarea nesfârșită de iterații (enumerare infinită a acelorași combinații de bază ale celulelor ocupate). De regulă, în problemele practice de transport, cum ar fi mersul cu bicicleta nu are loc; cu toate acestea, să fie conștienți de faptul că există reguli speciale pentru a iesi din bucla în cazul în care bucla se va întâmpla în continuare. În absența unei metode potențial de degenerare finit și conduce la un plan optim de transport pentru un număr finit de pași.