1.3. Metode pentru elaborarea unui plan inițial de bază
În ceea ce privește alte probleme de programare liniară, procesul iterativ pentru găsirea unui plan de sarcini optim de transport începe cu un plan de sprijin.
Luați în considerare sistemul de constrângeri (2) și (3) al problemei de transport. Conține mnemn necunoscute și ecuații m + n,
Legat de relația (4). Dacă combinăm ecuațiile subsistemului (2) și subsistemului (3) separat, obținem două ecuații identice. În tabel, această adăugire este echivalentă cu adăugarea numită a coloanelor și adăugarea de rânduri.
Prezența în sistem a constrângerilor a două ecuații identice indică dependența sa liniară. Dacă una dintre aceste ecuații este aruncată, atunci, în general, sistemul de constrângeri trebuie să conțină ecuații lineare independente m + n-1, deci un plan de suport nondegenerat al problemei de transport conține componente pozitive m + n-1 sau transport.
Astfel, dacă în orice mod se obține un plan de suport nondegenerat al problemei de transport, atunci în matrice
(Xij) (i = 1, 2.m; j = 1, 2.n) valorile componentelor sale (tabelul 2) sunt doar pozitive
M + n-1, iar cele rămase sunt egale cu zero.
Dacă starea sarcinii de transport și planul de sprijin sunt înregistrate sub forma unui tabel, celulele în care se află traficul non-zero sunt numite ocupate, iar restul sunt neocupate.
Celulele ocupate corespund necunoscutelor, iar pentru un plan de suport nondegenerat numărul lor este
M + n-1. Dacă constrângerile problemei de transport sunt scrise sub formă de (2) și (3) atunci, după cum se știe, un sistem de vectori independenți liniar corespunde necunoscutului de bază inclus în planul de suport.
Orice plan pentru o sarcină de transport care conține mai mult
M + n-1 ocupate de celule, nu sunt suport, deoarece aceasta corespunde unui sistem dependent de vectori liniar. Cu acest plan, întotdeauna este posibilă construirea unei buclă închisă în tabel, prin care numărul celulelor ocupate este redus la m + n-1.
Un ciclu este un set de tipuri de celule (i1 j1) (i1 j2) (j2 i2) (j1 im), în care două și numai două celule vecine sunt aranjate într-o coloană sau un rând al tabelului, acesta din urmă celula este în același rând sau coloană, , ca prima.
În cazul în care o celulă ocupată, determinarea unui plan de referință pentru un non-degenerat, prin urmare, aciclic, atașați orice celulă neocupată, planul devine o referință, există un singur ciclu, toate nodurile cu excepția unuia, sunt angajați în celule.
Există mai multe scheme simple pentru construirea unui plan inițial de referință pentru sarcina de transport.
La compilarea planului inițial de referință prin metoda unghiului nord-vest, costul transportului unei unități nu este luat în considerare, astfel încât planul construit este departe de a fi optim, primirea căruia este asociată cu o cantitate mare de lucrări de calcul. Prin urmare, metoda utilizată este utilizată în calculele computerizate.
Atunci când se folosește metoda costului minim, stocurile de furnizori sunt redistribuite consumatorilor la costuri minime. și în metoda dublă de preferință de redistribuire, acestea sunt de preferință produse prin acele celule ale căror costuri sunt minime pentru ambii furnizori. și pentru consumatori.
Costul planurilor obținute prin metodele de cost minim și dublă preferință este mai mic decât costul planului obținut prin metoda colțului nord-vestic, deci ele sunt mai apropiate de cea optimă.
Între ele, metodele de cost minim și dublă preferință sunt echivalente, ele sunt ușor de programat. Planurile rezultate sunt ajustate la metoda optimă de potențial.
1.4. Conceptul de potențial și ciclu
Dacă planul de transport X * = (x * ij) o este optim, atunci acesta corespunde unui set de m + n numere Ui * și Vj *. condiții satisfăcătoare
(i = 1, 2, 3, m, j = 1, 2, 3 n).
Numerele Ui * și Vj * sunt numite potențialul furnizorilor și respectiv al consumatorilor.
Dovada. Problema transportului de minimizare a funcției liniare Z = sub constrângeri
poate fi considerată dublă față de o problemă inițială a programării liniare, ale cărei condiții sunt obținute printr-o schemă generală dacă la fiecare constrângere a formei xi1 + xi2 +. + Xin = ai în problema originală corespunde variabilei Ui (i = 1, 2 m) și fiecare tip de restricție x1j + x2j + xmj = bj variabila Vj (j = 1, 2 n), și anume, maximizarea funcției lineare f = sub constrângerile Ui + Vj Cij
(i = 1, 2, m, j = 1, 2 n).
Planul X * este planul optim al problemei duale, deci planul Y * = (Ui *, Vj *) este un plan al problemei inițiale și pe baza teoremei dualității
Pe baza teoremei privind problema duală, constatăm că restricțiile problemei inițiale, corespunzătoare componentelor pozitive ale programului optim al problemei duale sunt satisfăcute egalitate strictă, iar componentele corespunzătoare la zero, cum ar fi inegalitatea, t. E.
Rezultă din teorema de mai sus: pentru ca planul inițial de susținere să fie optim, trebuie îndeplinite următoarele condiții:
pentru fiecare celulă ocupată, suma potențialelor trebuie să fie egală cu costul unității de transport din această celulă:
pentru fiecare celulă neocupată, suma potențialelor trebuie să fie mai mică sau egală cu costul unității de transport din această celulă:
Dacă cel puțin o celulă neocupate nu satisface condiția (6), planul de bază nu este optim și ar putea fi îmbunătățită prin introducerea în vectorul bază corespunzătoare celulei, pentru care perturbate condiția de optimalitate (ex. E. Celula nevoie pentru a muta o anumită cantitate de unități de marfă ).
Astfel, pentru a testa optimitatea, este necesar mai întâi să construim un sistem de potențial.
Pentru a construi un sistem de potențial, folosim condiția
unde Cij este costul transportului unității de sarcină a celulei ocupate în rândul i și coloana j.
Un sistem potențial poate fi construit numai pentru un program de suport nondegenerat. Un astfel de plan conține m + n-1 ecuații liniar independente de forma (5) cu n + m necunoscute. Ecuațiile sunt mai puțin decât cele necunoscute, deci sistemul este nedefinit, iar unu necunoscut (de obicei Ui) i se dă o valoare zero. După aceasta, celelalte potențiale sunt determinate în mod unic.
Fie ca potențialul Ui să fie cunoscut; Apoi din (5) rezultă că
Dacă se cunoaște potențialul Vj. apoi de la aceeași egalitate pe care o avem
Astfel, pentru a determina potențialul necunoscut din valoarea Cij a celulei ocupate, potențialul cunoscut ar trebui să fie scăzut.
Un set este o colecție arbitrară de transport de masă de transport.
Un lanț este numit un astfel de set, când fiecare pereche de celule vecine din lanț este situată fie într-o singură coloană, fie într-o singură linie.
O buclă este un lanț a cărui elemente extreme sunt fie într-o singură linie, fie într-o coloană.
Criteriul de optimizare a soluției de bază a problemei transportului
Distribuția de bază a alimentării este optimă dacă și numai dacă estimările tuturor celulelor libere sunt mai mari decât zero. Pentru celulele libere, se construiește o buclă, iar la vârfurile acestui ciclu se aranjează o secvență de semne alternative, începând cu semnul plus din celula liberă. Pentru factorii de cost ai tabelului de aprovizionare, în fiecare rând și fiecare coloană, trebuie adăugați astfel de numere (potențiale) încât factorul de cost din celulele umplutură să devină zero.
Factorii de cost rezultând celulele libere sunt egale cu estimările acestor celule.
1.6. Metodă distributivă pentru rezolvarea problemei de transport
Una dintre cele mai simple metode pentru rezolvarea problemei de transport este metoda de distribuire.
Să se găsească soluția inițială de suport pentru problema de transport și valoarea funcției obiective pe această soluție Z () să fie calculată. Prin teorema, pentru fiecare celulă liberă din tabelul cu probleme se poate construi un singur ciclu care conține această celulă și o parte a celulelor ocupate de soluția de susținere. După ce a desemnat acest ciclu și a efectuat schimbarea (redistribuirea încărcăturii) de-a lungul ciclului cu o sumă =, se poate obține o nouă soluție de suport X2.
Determina modul de schimbare a funcției obiectiv în timpul tranziției la o nouă soluție de suport. La schimbarea sarcinii unitate pe un ciclu corespunzător celulei (l, k), incrementarea funcției obiectiv este egal cu diferența dintre cele două sume: =, unde - suma costurilor de transport a unităților de marfă din ciclul celulelor ciudat, marcate cu „+“ - suma costurilor de transport unităților de transport în chiar celule ale ciclului marcat cu un semn
Celulele marcate cu „+“ valoarea sarcinii adăugată, ceea ce conduce la o creștere Z funcției obiectiv (), ca și în celulele marcate cu „-“, valorile de sarcină sunt reduse, ceea ce reduce valoarea funcției obiectiv.
Dacă diferența dintre sume pentru o celulă liberă (l, k) este mai mică decât zero, adică 1 2 3 Vezi toate
Arta similara:
Soluții optime care utilizează sarcini de transport liniare
parte a sarcinilor complexe, optimizate Fig. 2.1. Tipuri de sarcini de transport În sarcina deschisă cu resurse excesive. + Срр) d) în anumite cazuri, atunci când se rezolvă problemele de transport deschise, este permisă utilizarea sumei ca criteriu.
Generalizarea sarcinilor de transport multidimensionale
Hârtie termică >> Modelarea economică și matematică
containere în vehicule specializate: vagoane deschise, on. rezolvarea problemelor apărute în sistem, în procesul de funcționare a acestuia. 2. Reprezentarea structurală a unei sarcini de transport pe mai multe perioade. O problemă de transport cu mai multe perioade.
Declarație privind sarcina de transport cu scop general
de la afirmația problemei. Limitările sarcinii vor lua forma: Aceasta este condiția pentru rezolvarea problemelor de transport închise și deschise (ZTZ.). Evident, pentru rezolvarea problemei 1 este necesar.
Activitate de transport (8)
egalitatea nu este respectată, atunci problema este numită deschisă. Pentru resheniyatransportnoyzadachi nevoie de ea să fie. prin referință. [30] Decizia prin metoda simplex → metoda Reshenietransportnoyzadachi Transportnuyuzadachu simplex poate fi, de asemenea, rezolvată.
Activitate de transport (7)
vom examina soluția pentru problemele de transport utilizând Microsoft Office Excel. Ne este dat o sarcină. Pentru a rezolva problema de transport în Excel.
Articole similare
-
Algoritm pentru rezolvarea problemelor legilor din Kirchhoff
-
Algoritm pentru rezolvarea problemelor legilor din Kirchhoff - fizica acasă
Trimiteți-le prietenilor: