Biblioteca electronică »Informatică» Declarația problemei de transport a programării liniare
Metoda simplex pentru rezolvarea problemei de programare liniară este universală și poate fi utilizată pentru a rezolva astfel de probleme. Cu toate acestea, există anumite tipuri de probleme de programare liniară care, datorită unor particularități ale structurii lor, permit o soluție în moduri mai simple. Acestea includ, în special, așa-numita problemă de transport.
Problema clasică de transport a programării liniare este formulată după cum urmează.
Există puncte de plecare: A1. A2. Am. în care stocurile de mărfuri omogene (mărfuri) sunt concentrate în cantitate, respectiv, a1. a2. am unit. În plus, există n destinații: B1. B2. Bn. care au aplicat pentru b1, respectiv. b2. bn elemente.
Se presupune că suma tuturor comenzilor este egală cu suma tuturor stocurilor:
Costul transportului unei unități de mărfuri de la fiecare punct de plecare Ai la fiecare destinație Bj este cunoscut. Tabelul (matricea) costurilor de transport cij este dat:
Este necesar să se facă un astfel de plan de transport, în care s-ar fi împlinit toate cererile, iar costul total al tuturor transporturilor a fost minim.
Cu o astfel de afirmație a problemei, indicatorul eficienței planului de transport este costul; astfel încât sarcina prezentată este mai precis numită sarcina de transport prin criteriul valorii.
Să dăm acestei probleme o formulă matematică. Fie xij cantitatea de încărcătură trimisă de la punctul de plecare i la Ai către destinația j Bj (i = 1.m; j = 1.n). Variabile non-negative x11. x12. xmn (numărul care este în mod evident egal cu m xn) trebuie să îndeplinească următoarele condiții:
1. Cantitatea totală de mărfuri expediate din fiecare punct de plecare către toate destinațiile trebuie să fie egală cu stocul de marfă din acest punct. Acest lucru ne va oferi condiții de egalitate m:
unde semnul "sumă dublă" înseamnă că suma este peste toate combinațiile de indici (i = 1. m; j = 1. n), adică pentru toate combinațiile de puncte de plecare cu destinații.
Funcția (3.31) este liniară, iar restricțiile (3.29), (3.30) sunt, de asemenea, liniare. Înainte de noi - o problemă tipică de programare liniară cu constrângeri-egalități (OPLP).
Ca orice altă problemă de programare liniară, ar putea fi rezolvată printr-o metodă simplex, dar această problemă are unele particularități care fac posibilă o rezolvare mai simplă. Motivul este că toți coeficienții variabilelor din ecuațiile (3.29), (3.30) sunt egali cu unul. În plus, structura relațiilor dintre condiții este importantă. Nu este dificil să verificăm faptul că nu toate ecuațiile m + n ale problemei noastre sunt independente. Într-adevăr, adăugând împreună toate ecuațiile (3.29) și toate ecuațiile (3.30), trebuie să obținem același lucru, în virtutea condiției (3.28). Astfel, conditiile (2), (3) sunt legate printr-o dependenta lineara, si de fapt din aceste ecuatii doar m + n -1, in loc de m + n sunt independente liniar. Prin urmare, rangul sistemului de ecuații (3.29), (3.30) este egal cu
și, prin urmare, este posibilă rezolvarea acestor ecuații în raport cu variabilele de bază m + n-1, exprimându-le prin cele libere rămase.
Să calculam numărul de variabile libere. Este egal cu:
Știm că în problema programării liniare soluția optimă este atinsă într-unul dintre vârfurile SDT, unde cel puțin (m -1) (n -1) valorile lui xij ar trebui să fie zero.
Suntem de acord cu terminologia. Valorile xij ale numărului de unități de marfă trimise de la punctul Ai la punctul Bj vor fi denumite transport.
Orice set de valori (xij) (i = 1.m; j = 1.n) va fi numit un plan de transport. sau doar un plan.
Planul (xij) va fi numit admisibil. dacă îndeplinește condițiile (3.29), (3.30) (așa-numitele "condiții de echilibru"): toate ofertele sunt satisfăcute, toate stocurile sunt epuizate.
Vom numi planul admisibil drept unul de susținere. dacă nu există mai mult de r = m + n -1 transporturi de bază xij în ea. iar restul de transport este zero.
Planul (xij) va fi numit optim. dacă el, printre toate planurile admise, conduce la cel mai mic cost al întregului trafic.
Ne îndreptăm acum spre prezentarea metodelor de rezolvare a problemei de transport (TOR). Aceste metode nu necesită manipulare cu tabele simplex, ci sunt reduse la operații mai simple, direct cu tabelul, unde într-o anumită ordine toate condițiile TK sunt scrise. Noi numim o astfel de masă o masă de transport.
Înregistrează tabelul de transport
- punctele de plecare și de destinație,
- stocurile disponibile la punctele de plecare,
- cererile depuse de punctele de destinație,
- Costul transportului de la fiecare punct de plecare către fiecare destinație.
Vom pune costul transportului în colțul din dreapta sus al fiecărei celule astfel încât în celula în sine, atunci când transportați planul, să transportați transportul xij.
O masă de transport eșantion este prezentată în Tabelul 3.8.
Pentru scurt timp, în viitor vom desemna punctele de plecare - PO, puncte de destinație - PN. În colțul din dreapta sus al fiecărei celule, este indicat costul transportului unei unități de mărfuri (marfă) de la PO Ai la PN Bj. În coloana din dreapta există stoc de mărfuri în fiecare software, în linia de jos - ordinele prezentate de fiecare PO. Pentru T3, cantitatea de inventar este egală cu suma sumelor licitate; valoarea totală a acestei sume este înscrisă în celula din dreapta jos a tabelului.
Mai sus, am arătat că rangul sistemului de ecuații constrângeri-constrângeri este r = m + n-1, unde m este numărul de rânduri și n este numărul de coloane din tabelul de transport. Prin urmare, în fiecare plan de referință, inclusiv cel optim, nu vor fi transmise mai mult de m + n -1 de la zero.
Celulele (celulele) din tabelul în care vom scrie aceste transporturi nonzero, suntem de acord să numim cele bazale. iar restul (gol) sunt gratuite.
Astfel, decizia TOR a fost redusă la următoarele. Găsiți astfel de valori ale transporturilor pozitive, care, atunci când sunt aplicate pe celulele de bază ale mesei de transport, ar îndeplini următoarele condiții:
- Cantitatea de transport pe fiecare rând al mesei trebuie să fie egală cu stocul acestui software;
- Valoarea traficului din fiecare coloană trebuie să fie egală cu aplicarea acestei PN;
- costul total al transportului este minim.
În viitor, toate acțiunile pentru găsirea unei soluții la TK vor fi reduse la transformarea tabelului de transport 3.8.
În descrierea acestor transformări, va fi convenabil să folosim numerotarea celulelor de masă (cum ar fi numerotarea celulelor de șah). O celulă (Ai, Bj) sau, pe scurt, o celulă (i, j) vom apela o celulă în coloana i și a coloanei j din tabelul de transport. De exemplu, celula din stânga de sus va fi notată (1,1), stând sub ea (2,1), etc.
3.5.2. Găsirea unui plan de asistență
Soluția problemei de transport, ca orice problemă de programare liniară, începe cu găsirea unei soluții de sprijin sau, după cum vom spune, a unui plan de sprijin. Spre deosebire de cazul general al OPLP cu constrângeri arbitrare și funcție minimalizată, soluția TS există întotdeauna.
Construirea unui plan de sprijin.
Folosim așa-numita "metodă de colț nord-vestic". Va fi mai ușor să explicăm acest lucru cu un exemplu concret.
Exemplul 1. Termenii TK sunt specificați în tabelul de transport (vezi Tabelul 3.9)
Articole similare
Trimiteți-le prietenilor: