Sarcina de transport - pentru a învăța cum să împerecheați!

metodă de programare optimă este utilizată în rezolvarea obiectivelor economice și tehnico-economice, cum ar fi organizarea specializării raționale și a cooperării întreprinderilor, cele mai bune industrii de relații industriale și zone, distribuția teritorială bazată pe știință a producției sociale, și altele.

O zonă separată în programarea optimă este direcția de a combina studiul diferitelor probleme tehnice și economice de utilizare a capacității de tăiere rațională a materialelor, locația cea mai avantajoasă din depozitarea materialelor, depozitul, atașamentul consumatorilor furnizorilor, și așa mai departe. N.

Problema generală a acestor probleme este întrebarea cum să utilizeze cel mai bine resursele disponibile, cum să le distribuie rezultatul pentru a obține efectul maxim.

Programarea optimă este o metodă de rezolvare a problemelor economice, care să permită să efectueze alocarea mai rațională, optimă a resurselor.

Printre problemele de programare optime cel mai deplin dezvoltate și aplicate în practică, este o problemă de transport, esența care constă în modul în care produsele omogene (nisip, pietriș, ciment, cărămizi și așa mai departe. D.), cu sediul în Punta de plecare (depozite, cariere, fabrici ), distribuite în rândul consumatorilor (șantierele de construcții, instalații de fabricare a). la suma costului transportului de mărfuri și distanța totală parcursă (tone-kilometri) ar fi minime.

Există diferite moduri de a rezolva problema de transport: o metodă potențială, care să permită termeni, metoda de chirie diferențiale, metode simplex, și altele.

Scopul acestei lucrări de laborator este dezvoltarea practică a uneia dintre metodele de rezolvare a problemei transportului - potențialul metodei. Acest program vă va ajuta - un antrenament individual, interactiv și simulator - „Idiotul“

1. Declarația a problemei de transport.

In M punctele de plecare ale unui stoc omogen de produs concentrat

O cantitate (1). și (2). și (m) unitățile de produs trebuie să distribuie N într-o cantitate de consumatori: (1). în (20). în unități (n). Notăm oricare dintre revendicările de origine (furnizor) prin A (I). și destinația (consumator) prin B (J). Costul de transport pe unitatea de producție din punct-I-lea de origine la destinatie -ty J - C (ij) (tabelul 1).

Cantitatea de produs transportat de la punctul I-lea de plecare la destinație J -ty egal X (ig)

Planul de transport. Cazul general.

Sarcina este de a determina cantitatea de produs X (i, j). transportat pe toate rutele (i, j), sub rezerva minimului din costul total al transportului.

Formularea matematică a problemei sau funcția obiectiv

C = # 931; # 931; C (i, j) X (i, j) = min

Condițiile de limitare pentru această problemă sunt după cum urmează:

1) suma totală a livrărilor de la toți furnizorii M A (I) utilizatorul B (J) ar trebui să fie egală cu nevoile sale m. E.

2) volumul ofertei total A (i) toate N-lea consumatorii furnizor trebuie să fie egal prezența de la furnizorul t. E.

3) volumul de trafic nu ar trebui să fie negativ. t. e.

O condiție suplimentară: resursele totale ale furnizorilor sunt nevoile generale (fonduri) ale consumatorilor.

Sarcinile care satisfac această condiție, se referă la cele de tip închis, iar dacă nu - să se deschidă.

Deschideți sarcina poate fi întotdeauna ținute închise la introducerea de furnizor fictiv (utilizator), cu o marjă fictivă (cerința) și transport fără costuri.

Problema de transport se reduce la rezolvarea unui sistem M + n ecuații liniare de programare liniară cu n variabile M *.

schema de transport este optimă în cazul în care se obține cu condiția cererea de aprovizionare completă la un cost minim de punere în aplicare a volumului de trafic. Indicatori ai criteriului optimalitate în astfel de probleme este costul de transport al acestor produse. În unele cazuri, distanța de transport poate fi utilizat ca un criteriu.

2. Soluția problemei transportului cu potențial

Decizia de o potențială problemă constă în două etape consecutive:

1) asigurarea unei baze (de pornire), planul inițial de transport;

2) plan de îmbunătățire consistentă de bază la optim.

2.1. Construirea unui plan de bază de colțul de nord-vest. (Metoda Diagonal)

Avantajul acestei metode este formalizare riguroasă, lipsa - este departe de planul de bază optim, ceea ce crește numărul de iterații (tabelul 2)

Completarea planului de bază al matricei începe cu celula din stânga-sus (nord-vest). Se compara valoarea (marja) și vânzător (1), la cerința consumatorilor în (1). Cel mai mic dintre aceste valori este luată ca valoarea furnizorului de transport A (1) Controlul în consumator (1) și este scris în celulă (1,1). t. e.

Construirea unui plan de bază de colțul de nord-vest

Bold - volume de livrare

De obicei - completarea ordinului.

Dificultatea de a rezolva problema este determinată în mare măsură de construcție rațională a planului de bază, aceasta depinde de numărul de pași (iterații) necesare pentru soluția optimă.

O marjă (1) și în necesitatea (1) a redus cu valoarea X de transport (1,1). Ca rezultat, în apar celulele matricei, sau pentru care A (1) = 0 sau V (1) = 0. Astfel de celule nu sunt numărate (barat) în planul de construcție ulterioare. În continuare, poziția următoare celulele de nord-vest și umplerea acesteia se realizează, metoda descrisă mai sus.

Planul de bază va fi construit în cazul în care:

2.2. Construirea unui plan de bază cu costuri mai mici.

Această metodă oferă un plan de bază aproape de optim. In toate celulele matricei (în colțurile lor de sus dreapta) a făcut costul transportului unității de marfă al i-lea furnizor k j-acel utilizator.

Spre deosebire de metoda colțului de nord-vest a planului de construcție de bază începe cu umplerea celulei cu cel mai mic cost, precum și toate operațiunile asociate cu acestea nu se pot distinge de metodele descrise colt nord-vest.

Construirea unui plan de bază cu costuri mai mici.

In centrul celulei - volumul ofertei,

În colțurile inferioare - secvența de umplere,

În colțurile de sus - costul transportului.

2.3.Proverka și ajustarea planului de bază.

Metoda de potențiale precum și o serie de alte metode de programare liniară impune ca planul de bază și toate versiunile ulterioare îndeplinesc condițiile:

1) numărul de valori X (i, j), diferite de celule (matrice umplut cu zero), trebuie să îndeplinească condiția:

2) umplut cu matrice de celule de bază trebuie să fie dispuse astfel încât să asigure legătura lor reciprocă, și anume în fiecare rând are cel puțin o celulă de bază, care este într-o coloană în care există cel puțin o celulă de bază. Acest aranjament permite celulelor de bază ale ligament, care este necesar pentru a aborda problema potențială a metodei;

3) Planul de bază nu trebuie să conțină bucle închise, t. E. Dacă ne îndepărtăm de matrice, începând cu o bază sau celule și să facă transformă pe celule de bază, astfel încât este imposibil să se întoarcă la celula originală.

În cazul în care nu prima condiție, t. E. de N

În acest caz, numărul de celule de bază sunt furnizate în conformitate cu prima condiție de încărcare cantitatea necesară de „goale“ ( „liber“) livrările de celule cu zero [X (ij) = 0]. că în calculele ulterioare vor fi considerate încărcate (celule de bază fictive).

Amplasarea celulelor manechinului trebuie să îndeplinească condițiile specificate mai sus (revendicarea 2 și 3).

3.Optimizatsiya planul de potențial metodă.

Optimizarea planului de transport prin efectuarea în mod repetat un anumit număr de etape, fiecare fiind format din trei etape:

I. calcularea potențiale,

II. Planul de inspecție pentru optimalitate;

III. redistribuire a consumabilelor.

Atunci când există un sistem optim de numere de transport planul format din constructii furnizori (rânduri) U (i) și potențialele consumatori (coloane) V (j). care îndeplinesc simultan următoarele două relații:

1) pentru celulele de bază încărcate [X (i, j)> 0]

2) pentru celulele neîncărcate (libere) [X (i, j) = 0]

Rezultă că, dacă un astfel de sistem este un potențial U (i) și V (j) există, atunci planul optim și dacă nu există un astfel de sistem, nu este cel mai bun plan.

3.1. CALCULAREA POTENTIAL.

Potențialele sunt calculate pe baza ipotezei că planul estimat (de exemplu, bază) este optimă. Apoi, potențialul liniilor U (i) și coloana V (j) sunt la celule de bază (încărcate) folosind condiția (3). În această pre-presupus că unul dintre potențialele sau U (i). sau V (j) este luată egal cu 0 (tab. 4)

Evaluarea și selectarea planului de promițătoare optime celulelor.

În celula colțul din stânga - potențialul de celule;

La unghiuri drepte - costul transportului; semna> Celulele marcate ale căror potențiale sunt mai mari decât costul, semnul ### celula prospectiv.

3.3. Redistribuirea a volumului de livrări. (Planul de îmbunătățire a)

În cazul în care planul nu este optim, este necesar să-l îmbunătățească pentru a redistribui volumele de livrări, astfel încât valoarea totală a transporturilor a scăzut.

Redistribuirea volumelor în următoarea ordine:

I. 1) determinat de celula „promițătoare“ - o celulă goală, pentru care diferența dintre potențialul celulelor, P (i, j) și valoarea sa C (i, j) este cea mai mare (Tabelul 5)

II. 2) planificate ciclu de redistribuire - un viraj vicios. care începe și se termină cu celula „perspectivă“, iar colțurile sale sunt situate pe celulele încărcate (Tabelul 6).

III. 3) toate celulele ciclu de transfer unghiular sunt atribuite alternativ + și - semne. începând cu „promițătoare“, care este întotdeauna asociată semnul +; în cazul în care unghiulară CITE atribuite dreapta; în fiecare rând și coloană numărul celulei unghiulare cu + va fi egal cu numărul de celule cu semnul -;

IV. 4) se adaugă minimul livrărilor la celule negative sau scăzute din volumele de celule unghiulare în funcție de semnul lor.

V. Ca urmare a acestei redistribuiri transformă un plan nou și îmbunătățit, și plasarea celulelor umplute variază datorită faptului că celula „pe termen lung“ sa umplut și au umplut colț - a fost liberă (Tabelul 6). Planul rezultat testat pentru maniera optimalitate descrisă mai sus.