Determinarea planului optim a problemei de transport - studopediya

Cele mai frecvente este metoda de potențiale.

Teorema. Dacă dintr-un program de sprijin X * = [x * y] problema de transport și există un număr astfel încât pentru xij> 0 și xij = 0 pentru toți, atunci X * - planul optim.

Numerele sunt numite potențiale, respectiv, punctele de plecare și de destinație.

Această teoremă ne permite de a construi un algoritm pentru rezolvarea problemei de transport:

1. Găsiți un program de sprijin al problemei transportului una dintre metodele discutate mai sus.

2. Se calculează potențiale puncte de plecare și destinații, folosind relația:

unde CJI - tarife, în picioare în celulele umplute din tabel condițiilor probleme de transport.

Rezultatul este un sistem de ecuații liniare constând din (m + n-1) ecuații cu (m + n) - necunoscut, adică sistemul este nesigur.

Pentru ao rezolva, una dintre variabilele atașate la o valoare arbitrară și în mod constant găsi necunoscutele rămase (de exemplu, ia în considerare # 945; 1 = 0)

3. Pentru toate celulele sunt libere de # 945; ij din condiția:

Dacă printre numerele # 945; ij nu este pozitiv, adică toate # 945; ij ≤0, găsit programul de sprijin este optim.

În cazul în care pentru unele celule libere # 945; ij> 0, planul poate fi îmbunătățit.

4. Construcția planului îmbunătățit:

Dintre toate numerele # 945; sunt necesare ij> 0vybirayut maximă și caseta corespunzătoare acestui număr. Acest lucru se poate face prin bucla de ciclism (ciclu)

În cazul în care linia întreruptă formând o buclă intersectează punctul apex de auto-intersecție nu este (Fig. B)

În cazul în care programul de sprijin a fost construit în mod corect, numai o singură cale ciclică poate fi construit pentru orice celule libere.

Pentru a merge la un nou program de sprijin, atunci când se construiește circuitul ciclic, este necesar să se efectueze deplasarea încărcăturii în interiorul celulei asociate contur circular, adică punerea în aplicare a ciclului de conversie de deplasare

Lui sunt următoarele reguli:

1. Fiecare celulă inclusă într-o buclă ciclică este atribuit un anumit semn, celula liber semnul „+“, în timp ce restul alternativ „-“, „+“.

2. Celulele libere sunt transferate dintr-un număr mai mic hij. stând în picioare în „-“ celule. Același număr se adaugă la numărul în „plus“ celule și se scade din numerele de celule cu care se confruntă „minus“. Ca rezultat, celula liber selectat devine ocupat, și „minus“, a celulei, în care se afla un număr minim de hij - gratuit.

La schimbarea ciclului de conversie, numărul de celule ocupate trebuie să rămână constantă, egală cu (m + n-1).

În cazul în care celulele „minus“ există două sau mai multe numere identice de hij. liber o celulă, iar restul este considerată muncă contingent cu trafic zero.

Atunci când construirea unui program de sprijin sau în procesul de soluționare a problemei poate fi obținut prin planul degenerat. Pentru a evita acest caz looping. Planul trebuie să conducă la un non-degenerat, pentru care celulele goale (de preferință, cu rate minime de trafic) umplut transport arbitrar mici, adică cele introduse în aceste celule, de exemplu, considerate convențional utilizate numărul E = 0,001, iar celulele. La determinarea costului de transport și să ia în planul optim E = 0.

3. Planul superior verificat din nou pentru optimalitate, adică, mergeți la pasul 2.