Deschideți modelul de rezolvat prin aducerea modelului închis.
În cazul în care (a) atunci când rezervele totale depășesc cererea totală, utilizatorul fictiv introdus Bn + 1. care are nevoie de bn + 1 =
. În cazul (b), atunci când cererea totală depășește rezervele totale, a introdus un Am inactiv + 1. Rezervele sunt + 1 =
Costul de transport al unității de marfă ca un client fictiv, iar costul unităților de transport pe un furnizor fictiv se presupune a fi zero, deoarece, în ambele cazuri, bunurile nu sunt transportate.
După transformare problema ia forma unui model închis este rezolvată și mod normal. La o valoare egală a unităților de transport de marfă de la furnizori la fictive costurile de transport ale clienților pentru consumatori reale sunt minime, iar clientul va trimite o sarcină fals pe cel mai puțin profitabile furnizori. Același lucru este obținut în ceea ce privește o societate fictivă.
Înainte de a rezolva orice problemă de transport, trebuie să verificați mai întâi ce model îi aparține, și numai apoi face un tabel pentru a rezolva problema.
1.3. Metodele de preparare a programului de sprijin inițial
În ceea ce privește celelalte probleme de programare liniară, proces iterativ pentru identificarea unui plan optim a problemei de transport începe cu un program de sprijin.
Luați în considerare constrângerile de sistem (2) și (3) problema de transport. Conține necunoscutele m'n și ecuațiile de m + n,
relație asemănătoare (4). Dacă pliată separat subsistemul termwise ecuația (2) și subsistemul separat (3), obținem două ecuații identice. În plus, o astfel de tabel este echivalentă cu adăugarea termwise plus respectiv termwise de coloane și rânduri.
Că limitele sistemului de două ecuații identice arată dependența liniară. Dacă una dintre aceste ecuații aruncate, apoi, în general, constrângerile de sistem trebuie să conțină m + n-1 ecuații liniar independente cu
fost consecvent, suport nedegenerat sarcina de transport program cuprinde m + n 1-componente sau de transport pozitiv.
Astfel, în cazul în care, în orice mod de a obține un non-degenerat sprijinirea planului de transport problema, matricea
(Xij) (i = 1, 2 m; j = 1, 2 n) valorile componentelor sale (Tabelul 2) au fost pozitive doar
M + n-1, iar restul sunt zero.
În cazul în care starea problemei transportului și programul său de sprijin este înregistrat într-un tabel, celula, care sunt diferite de transport la zero, numit ocupat, iar restul - neocupat.
Celulele Salariați corespunde necunoscute, iar numărul programului de sprijin pentru un egal nedegenerat
M + n-1. Dacă limitările problema transportului scris sub forma (2) și (3), după cum se știe, de bază necunoscut, inclus în planul de bază, sistemul corespunzător de vectori liniar independenți.
Fiecare plan a problemei de transport, cu mai mult
M + n-1 angajat nu sprijină celulă, deoarece corespunde vectorilor de sistem liniar dependente. În acești termeni în tabel este întotdeauna posibil să se construiască o buclă închisă, prin care se reduce numărul de celule ocupate 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ă unele scheme simple de construcție a programului de sprijin inițial al problemei de transport.
La elaborarea planului de referință inițial de colțul de nord-vest a costului unitar de transport nu este inclus, astfel încât planurile de construcție este departe de a fi optimă, primirea care este asociat cu o cantitate mare de calcul de lucru. Prin urmare, metoda de mai sus este utilizată în calcule cu ajutorul unui calculator.
folosind metoda de stocuri minime furnizorilor de costuri sunt redistribuite consumatorilor la cel mai mic cost. și o metodă de preferințe duble redistribuție fabricate, de preferință, prin acele celule ale căror costuri reduse pentru ambii furnizori. și consumatori.
Costul planului, obținut prin valoarea minimă și mai mică decât dublul valorii preferință a planului elaborat de colțul de nord-vest, astfel încât acestea sunt mai aproape de optim.
Între o valoare minimă și metodele de preferințele duale sunt aceleași, ele sunt ușor de program. Planurile rezultate ajustate la metoda potențialului optim.
1.4. Conceptul de capacitate și ciclul
Dacă aveți de gând X * = (x * ij) sarcină o Transportul este cel mai bun, el are un set de m + n numere Ui * și Vj *. îndeplinește condițiile
(I = 1, 2, 3 m; j = 1, 2, 3 n).
Ui și Vj * * număr se numește potențiale, respectiv, furnizori și consumatori.
Dovada. problema Transportul minimizând o funcție liniară Z =
xij. 0 (i = 1, 2 m; j = 1, 2 n)
poate fi considerată ca o sursă dublă de o problemă de programare liniară, termenii care sunt obținute în cadrul regimului general, în cazul în care fiecare tip de restricție 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 =
(I = 1, 2. m; j = 1, 2 n).
X * este un plan pentru programul optim al problemei duale, astfel încât planul Y * = (Ui *, Vj *) este planul problemei originale, și pe baza teoremei dualitate
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, ¾ ca inegalitatea t. E.
Din această teoremă rezultă că, pentru a sprijini planul original a fost cel mai bun, trebuie să îndeplinească următoarele condiții:
a) pentru fiecare celulă ocupată de suma potențialelor trebuie să fie egală cu costul unitar de transport, în picioare în celulă:
b) Pentru fiecare celule neocupate suma potențialelor trebuie să fie mai mică sau egală cu costul unității de transport, care se afla in celula:
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 verifica optimalitate ar trebui să construiască mai întâi un potențial sistem.
Pentru a construi utilizarea potențială a stării sistemului
unde Cij ¾ costul unităților de transport marfă ocupate de celule din rândul i-lea și coloana j-a.
potențial sistem poate fi construit numai pentru programul de sprijin non-degenerate. Un astfel de plan include m + n-1 ecuații liniar independente de forma (5)
n + m necunoscute. Ecuații unul mai puțin decât necunoscutelor, astfel încât sistemul este nedefinit și unul necunoscut (de obicei, Ui) da zero. După aceea, restul potențialelor sunt determinate în mod unic.
Să cunoscut potențialul Ui; apoi din ecuația (5)
Dacă știți potențial Vj. o parte din aceeași ecuație, avem
Astfel, scade capacitatea de cunoscut pentru a determina potențialul necunoscut asupra celulelor ocupate CJI.
Set este un set arbitrar de tabel de transport trafic.
Lanț numit astfel de seturi în cazul în care fiecare pereche de celule adiacente în lanț sau aranjate într-o singură coloană sau într-un singur rând.
Un ciclu este un lanț, dintre care elementele de capăt se află fie într-un rând sau într-o singură coloană.
1.5.Kritery soluție optimă de bază a problemei de transport
Alocarea de bază de aprovizionare este optimă dacă și numai dacă evaluarea tuturor celulelor disponibile este mai mare decât zero. Pentru ciclul de conversie de construcții cu celule libere, iar la nodurile acestui ciclu este răspândit secvență de simboluri intercalate, începând cu un semn plus în celulă liberă. Pentru a furniza tabelul coeficienților de costuri în fiecare rând și fiecare coloană trebuie să fie adăugate astfel de numere (potențialurilor) raportul în celule umplute costa devin egale cu zero.
Rezultatele astfel coeficienții de intrare sunt celule estimate libere ale acestor celule.
1.6. Metoda de distribuție pentru rezolvarea problemei de transport
Una dintre cele mai simple metode de rezolvare a problemei de transport - metoda de distribuție.
Să presupunem, pentru problema transportului găsit soluția inițială de suport
și valoarea calculată a funcției obiectiv pentru decizia Z (
). Prin Teorema pentru fiecare fără probleme celulele din tabel se poate construi doar o buclă care conține celula și o parte din celulele ocupate de soluția de referință. Înțelesul ciclului și pentru a efectua deplasare (redistribuire a sarcinii) a ciclului cu o sumă
, puteți obține o nouă soluție de referință 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:
- suma costului transportului unităților de marfă din ciclul impar de celule marcate cu „+“
- suma costurilor de transport a unităților de încărcare în ciclul chiar a celulelor marcate cu
Celulele marcate cu valoarea sarcinii „+“ a adăugat, ceea ce duce la o creștere a funcției obiectiv Z (
) Și în celulele marcate cu „-“, valorile de încărcare sunt reduse, ceea ce reduce valoarea funcției obiectiv.
Dacă diferența însumează pentru celulele libere (l, k) este mai mică decât zero, adică
<0, то перераспределение величины
ciclul respectiv va reduce valoarea Z (
, și anume soluția de referință poate fi îmbunătățită. În cazul în care valoarea
, numitele estimări. pentru orice problemă de transport gratuit al celulelor din tabel sunt non-negative, atunci valoarea funcției obiectiv nu poate fi redusă, iar soluția de referință este optimă. Prin urmare,
starea optimalitate este metoda de distribuție
Pentru a rezolva problema de transport a metodei de distribuție trebuie găsită soluția inițială de suport. Apoi, pentru următoarea celulă de referință (l, k) și se calculează evaluarea ciclului de construcție
. În cazul în care evaluarea unui non-negativ, trecerea la următoarea celulă disponibilă. În cazul în care evaluarea este negativ, este necesară punerea în aplicare compensate de valoarea ciclului
. Rezultatul va fi noua soluție de referință.
Pentru fiecare nou calcul soluții de referință a evaluărilor începe cu primele celule de masă gratuite. Dovada verificabilă de celule libere este recomandabil să se instaleze în ordinea crescătoare a costurilor de transport
, Deci, cum să rezolve problema de a găsi un minim.
2. Dezvoltarea și descrierea algoritmului pentru rezolvarea problemei
2.1. Declarație Semnificativ a problemei
Fii modelul economico-matematic al problemei. Găsiți distribuția optimă a costurilor minime de transport și aprovizionare. Distribuția inițială de consumabile pentru a efectua metoda din colțul de nord-vest.
În practică, aceste probleme sunt rezolvate, desigur, cu ajutorul software diferite, care pot simplifica în mod semnificativ activitatea și de a salva timp.
Să vedem cum acest lucru se poate face într-un mediu foi de calcul Microsoft Excel.
În aplicația de calcul tabelar Microsoft Excel pentru rezolvarea unor astfel de probleme este furnizat Solver. Efectuați următoarele lucrări pregătitoare pentru soluționarea problemei de transport prin utilizarea Solver în aplicația de calcul tabelar Microsoft Excel.
1. Tipul în gama A6 de celule: D8 valoarea cererii
2. Introduceți intervalul de celule A9: costuri de matrice D9.
3. Introduceți intervalul de celule E6: E8 stocurilor.
4. Celula de E9 decizii optime de ieșire
= SUMPRODUCT (A1: D3; A6: D8). Acest lucru se poate face cu ajutorul Expertului de funcții prin selectarea secțiunii. Funcția SUMPRODUCT matematică și specificând intervalul dorit.
Apoi, alegeți serviciul de comandă, caută soluții și să umple deschide dialogul de căutare soluțiile caseta.
În caseta de dialog Căutare, selectați caseta de validare soluții Opțiuni de modelul liniar. După apăsarea butonului. Rulați-a face motorul de căutare găsește cel mai bun plan de livrări de produse și costurile de transport corespunzătoare.
Soluția optimă a problemei de transport