3. Definiți conceptele: un subset de rute, o estimare mai mică a costului rutei, o constantă de turnare, o matrice cu cost redus, o penalizare pentru "neutilizare", un traseu optim.
4. În acest caz, atunci când rezolvăm problema vânzătorului care călătorește prin metoda branch-and-bound, este revenirea la pasul decizional anterior efectuat, returnați arborele?
5. De ce este metoda de ramură și limită numită "o metodă eficientă de căutare"?
Problema transportului (TOR) aparține unei clase speciale de probleme de programare liniară. Specificitatea modelului matematic al TZ permite, împreună cu metodele generale de rezolvare a problemelor LP, să se aplice metode speciale care să permită reducerea calculelor. Declarația TZ aparține lui Hitchcock.
Declarația problemei. Există puncte de producție m (depozite) ale unui singur produs, dat fiind producția de aluminiu la punctul i de producție. Există n puncte de consum ale acestui produs, bj este setat - volumul consumului (cererile depuse pentru furnizarea produsului) la punctul de consum j.
Punctele de producție sunt legate de punctele de consum printr-o rețea de drumuri cu anumite tarife pentru transport. Costul transportului unei unități de produs (încărcătură) de la punctul i de producție până la punctul j de consum este cij. Este necesar să se găsească planul optim de transport pentru produse, în care costurile de transport sunt minime, produsele sunt exportate complet din punctele de producție, iar cererea de produse este pe deplin satisfăcută.
Modelul matematic al problemei. Ca variabile, elementele matricei de transport sunt selectate :.
Fie - numărul de unități de produse exportate de la punctul i de producție până la punctul j de consum.
Primele constrângeri m specifică condiția: întregul produs este luat din fiecare punct de producție i. De exemplu (figura 1), de la primul punct de producție cu volumul producției a1, produsul poate fi transportat la punctul 1 de consum. Volumele de transport sunt necunoscute și se ridică la: - numărul de articole transportate de la primul punct de producție la primul punct de încălzire; - numărul de unități de produse transportate de la primul punct de producție la al doilea punct de consum; - numărul de unități de produse transportate de la primul punct de producție la punctul n de consum. Suma tuturor articolelor transportate ar trebui să fie egală cu a1. .
Următoarele restricții n specifică condiția: fiecare punct j de consum este furnizat cu tot produsul necesar.
Dimensiunea problemei :. Problema transportului este un caz special al problemei de programare liniară, în care toate constrângerile sunt de tipul egalității. Spre deosebire de cazul general al soluționării problemei LP, soluția optimă a problemei de transport există întotdeauna
Metode de soluționare. Ca o problemă de programare liniară, simplexul poate fi rezolvat prin metoda simplex []. Au fost de asemenea dezvoltate metode speciale (mai eficiente) de rezolvare a problemei transportului: metoda generalizată maghiară []; metoda colțului nord-vestic, metoda elementului minimal pentru găsirea planului de sprijin; metoda potențialilor pentru găsirea planului optim [].
Operațiuni de transport deschise și închise. Există două tipuri de TK: un TK deschis și un TK închis.
O problemă de transport este numită închisă dacă condiția de echilibru este îndeplinită. volumul total al producției este egal cu volumul total de consum:
Rețineți că modelul matematic () specifică o sarcină de transport închisă.
Un TK deschis poate fi specificat în două variante.
Prima opțiune. Volumul total al producției este mai mic decât volumul total de consum:
Pentru a rezolva problema transportului, este necesar să se reducă sarcina de transport deschis la cea închisă, pentru care se introduce un punct fictiv de producție m + 1 cu un volum de producție:
A doua opțiune. Volumul total al producției este mai mare decât volumul total de consum:
Pentru informații tip închise, introduceți un punct fictiv de consum n + 1 cu volumul de consum:
Starea sarcinii de transport este stabilită sub forma unei mese de transport (tabelul 1):
Elementele matricei planului de transport (celule, celule de masă) sunt numite de bază. dacă sunt diferite de zero; celulele zero ale mesei sunt numite libere.
Planul de transport este permis. dacă satisface condițiile de echilibru (): toate ofertele sunt satisfăcute, toate stocurile sunt epuizate.
Un plan fezabil este un plan de referință. dacă în acesta nu mai mult de r = m + n-1 transporturile de bază sunt diferite de zero, iar vagoanele rămase sunt egale cu zero. Dacă traficul non-zero este mai mic decât r = m + n-1. atunci un astfel de plan este numit un plan de sprijin degenerat.
Planul optim de transport este planul cu cele mai mici costuri din toate planurile de transport admise.
Metoda din colțul nord-vestic.
Etapa 0. Starea sarcinii de transport este stabilită sub forma unei mese de transport (tabelul 1).
Pasul 1. Verificați dacă condiția de echilibru () este satisfăcută. Dacă condiția de echilibru nu este îndeplinită, adică sarcina este deschisă, apoi este redusă la un tip închis.
Pasul 2. Creați un tabel al planului de transport (tabelul 2), în care sunt completate numai volumele de producție și volumul de consum. Apoi începeți să umpleți masa de transport din colțul din stânga (nord-vest). Când se umple, treceți de-a lungul liniei spre dreapta și în jos pe coloană. În celula situată la intersecția dintre primul rând și prima coloană, se pune numărul maxim de unități de produse permise prin restricții privind oferta și cererea :.
Să oferim, de exemplu, oferta primului producător (furnizor) să fie complet epuizată. Celulele rămase din primul rând sunt umplute cu zerouri și se deplasează de-a lungul primei coloane în jos. Celulele situate la intersecția primei coloane și al doilea rând este plasat numarul posibil cart maxim de unități permise constrângeri cerere și ofertă :. Dacă, de exemplu, atunci. Cererea primului consumator este satisfăcătoare. Celulele rămase din prima coloană sunt umplute cu zerouri și se deplasează de-a lungul liniei a doua spre dreapta. Prin completarea celulei la intersecția doilea rând și coloana a doua, trece la următoarea umplere Thr-tey celule a doua linie, fie coloana a doua. Procesul continuă până când propunerile sunt epuizate și cererea este complet satisfăcută. Ultima celulă umplută este în coloana n și în rândul m.
Exemplul 1. Determinați planul de referință prin metoda din colțul nord-vestic pentru sarcina de transport specificată în Tabelul. 3
volumul consumului de producție
La prima etapă, sunt verificate condițiile bilanțului. Volumul total al producției este: 200 + 40 + 110 = 350 unități convenționale; volumul total de consum este egal cu: 120 + 50 + 190 + 110 = 470. Prin urmare, T3 este unul deschis. Pentru reducerea sa la un tip închis, este necesar să se introducă un al patrulea punct de producție cu un volum de producție egal cu: = 470-350 = 120 unități convenționale. Deoarece punctul de producție este fictiv, costul transportului produselor de la acest punct la punctele de consum este zero (Tabelul 4).
volumul consumului de producție
În a doua etapă, creați o tabelă goală a planului de transport și începeți să îl umpleți (Tabelul 5).
volumul consumului de producție
Prima celulă este plasată: (Tabelul 5). Aplicațiile primului consumator sunt complet satisfăcute, restul celulelor din prima coloană sunt umplute cu zerouri. Restul producției din primul paragraf este: 200-120 = 80 de unități convenționale de marfă.
Apoi, deplasați-vă de-a lungul primului rând spre dreapta și completați celula (1,2) :. Aplicațiile celui de-al doilea consumator sunt complet satisfăcute, restul celulelor celei de-a doua coloane sunt umplute cu zerouri. Restul producției din primul paragraf este egal cu: 80-50 = 30 de unități convenționale de marfă.
Datorită volumului mare, acest material este plasat pe mai multe pagini:
1 2 3 4 5 6 7
Aboneaza-te la newsletter-ul nostru:
Știri interesante
Subiecte importante
Recenzii de servicii Pandia.ru
Proiecte pe tema:
Vatră acasă
Informații de referință
Educație și știință
Afaceri și Finanțe
tehnologiei
infrastructură
Articole similare
Trimiteți-le prietenilor: