§ 1. Declarația problemei de transport (TOR) pentru variabilele n
§ 2. Un exemplu de soluție la sarcina de transport
§3. Sarcini de transport prin diferite criterii
§4. Soluția sarcinii de transport în Excel
Numele "sarcina de transport" combină o gamă largă de sarcini cu un singur model matematic. Problema clasică a transportului este problema celui mai economic plan de transport al unui produs omogen sau a produselor interschimbabile de la punctele de producție la cele de consum, cel mai adesea fiind întâlnit în aplicații practice de programare liniară. Programarea liniară este una din secțiunile de programare matematică - un domeniu de matematică care dezvoltă o teorie și metode numerice pentru rezolvarea problemelor extremiste multidimensionale cu constrângeri.
Un număr mare de posibile opțiuni de transport face dificilă obținerea unui plan suficient de economic empiric sau expert. Aplicarea metodelor matematice și computaționale în planificarea transportului dă un mare efect economic. Problemele de transport pot fi rezolvate printr-o metodă simplă, totuși matricea sistemului de constrângeri al problemei de transport este atât de unică încât s-au dezvoltat metode speciale pentru rezolvarea ei. Aceste metode, precum metoda simplex, fac posibilă găsirea soluției inițiale de sprijin și apoi îmbunătățirea acesteia pentru a obține soluția optimă.
În funcție de modul de prezentare a condițiilor sarcinii de transport, aceasta poate fi reprezentată într-o formă de rețea (schematică) sau matrică (tabulară). De asemenea, sarcina de transport poate fi rezolvată cu restricții și fără restricții.
§ 1. Declarația problemei de transport (TOR) pentru variabile
Să presupunem că există mai mulți furnizori de produse omogene (fiecare cu un anumit stoc) și mai mulți consumatori ai acestui produs (cu nevoi cunoscute pentru toată lumea). De asemenea, este alocată o rețea de comunicații (drumuri, râuri, linii aeriene etc.), care leagă fiecare furnizor de fiecare consumator. La fiecare comunicare este stabilit prețul transportului - costul transportului unei unități de producție. Dacă orice comunicare este absentă, atunci credem că este, dar prețul transportului pe ea este egal cu infinitul (+ ∞). Acest acord va face neprofitabil să îl transporte și să excludă automat această comunicare din planul de transport.
Astfel, este necesar să se elaboreze un plan pentru transportul produselor de la furnizori către consumatori, astfel încât nevoile consumatorilor să fie îndeplinite prin exportul de bunuri de la furnizori. Scopul este de a minimiza costul total al tuturor transporturilor.
Sarcinile de transport sunt:
1) deschis m ≠ n (stocul total de produse disponibile de la furnizori nu coincide cu cererea totală de produse de la consumatori).
2) închis m = n (stocul total de produse disponibile de la furnizori coincide cu cererea totală de produse de la consumatori).
Metoda potențialelor "funcționează" numai pentru TK închis, iar TK închis este întotdeauna soluționabilă.
TK reduce deschis la TK închis prin adăugarea la stocul total al produselor sau nevoile totale de produse de unități egale cu necesarul total suma de rezervă și de producție de produse care lipsesc.
Problema de transport închis este formulată ca Problemă de programare liniară (APL) în forma următoare:
1. Optimalitatea este afectată în celulă (3.3). Îi vom acorda transport # 952;> 0 (+ # 952; înseamnă o creștere de # 952;).
2. Soldul exporturilor furnizorului 3 este încălcat (exporturile de 50+ # 952; care este mai mult decât stocul său!). Reduceți prin # 952; transportul în celula umplută a liniei 3 (este imposibil să se reducă cantitatea de celulă umplută, deoarece aceasta va duce la transportul negativ).
Să luăm în considerare acele celule ale ciclului în care scădem # 952; transport și să ia un minim de deductibile, avem-o min = 10.
Iar acest număr trebuie înlocuit în ciclu
§3. Sarcini de transport prin diferite criterii
Sarcina de transport pe criteriul timpului
Uneori există o situație în care, din punct de vedere al (TK), este necesar să se reducă la minimum costul transportului, dar timpul de îndeplinire a acestora (mărfuri exprese, transportul bunurilor perisabile, munca de "prim ajutor" etc.)
Sunt furnizori de m
încărcături omogene și n consumatori
mărfuri. Pentru fiecare pereche (
,
, pentru care mărfurile sunt transportate
. Este necesar să se realizeze un astfel de plan de transport, în care să fie exportate toate stocurile de furnizori, iar toate cererile consumatorilor vor fi pe deplin satisfăcute, iar cel mai mare timp de livrare a tuturor încărcăturilor va fi redus la minimum.
Problema alocării (metoda maghiară)
Există n tipuri de muncă și n muncitori. Fiecare lucrător poate efectua o anumită perioadă de timp (prețul lucrătorului). Este necesară distribuirea tuturor lucrărilor între toți lucrătorii, astfel încât timpul pentru realizarea lucrării să fie minim, iar fiecare lucrare este efectuată de un singur lucrător.
§4. Soluția problemei de transport în Excel
De exemplu, am considerat sarcina de transport pentru 2 depozite și 5 magazine.
· În celulele C4: C5 au fost înregistrate volumele de produse disponibile în 2 depozite.
· În celulele E5: I5 - cereri pentru produse primite de la magazine.
· În celulele B8: F9 - o matrice a costurilor de transport, care stabilește costul transportului de la primul depozit la depozitul J al unității de producție.
· În celulele B13: F14 - plan de transport - o matrice care specifică cantitatea de mărfuri transportate de la primul depozit la cel de-al J-lea. Distribuirea inițială a planului este stabilită în conformitate cu principiul "fiecare soră de pe cercel", distribuind în mod egal toate produsele disponibile în depozit către magazine. Aceste celule sunt reglabile și Solver trebuie să găsească o soluție mai potrivită prin modificarea valorilor din aceste celule.
· În celula D15 - a fost înregistrată funcția obiectivă:
· În celulele D17: H17 a scris restricțiile care specifică cerința pentru executarea exactă a aplicației fiecărui magazin. Ca de obicei, am scris formula corespunzătoare în primul dintre aceste celule:
Apoi am copiat-o. Când se copiază, formula se modifică automat, setând limita dorită. Este adevărat că trebuie să monitorizați orientarea corectă a datelor. De exemplu, în acest caz, formula trebuie copiată într-un rând, nu într-o coloană.
· Apoi am stabilit următorul grup de constrângeri. Aceste restricții îndeplinesc condițiile naturale pe care nu le puteți scoate din depozit mai mult decât există. Formula introdusă în celula D18 este:
Această formulă a fost copiată deja de coloană în celula D19. Etapa pregătitoare este finalizată - puteți apela Solver.
Când ați apelat Solverul și ați setat parametrii în caseta de dialog, sa efectuat o lucrare standard pentru a specifica o celulă cu o funcție țintă, o gamă de celule reglabile și setarea constrângerilor. Observați, pe lângă cele două grupuri de constrângeri, am specificat și restricțiile variabilelor întregi. Se presupune că produsele pot fi transportate numai de unități întregi - butoaie, saci, cutii. Astfel de restricții în Solver sunt create pur și simplu, - este suficient între operatorii care leagă părțile din stânga și din dreapta constrângerii să aleagă operatorul int. Uitați-vă la rezultatele lucrării mele:
Fig. 2.21. Window Solver în rezolvarea problemei de transport
Înainte de a da comenzii pentru a rezolva problema, am făcut setările în fereastra Opțiuni. În special, am activat casetele de selectare care indică liniaritatea modelului și pozitivitatea variabilelor. În plus, am crescut precizia rezolvării problemei întregi prin setarea ferestrei Toleranță la o valoare de 1% în loc de 5% implicit.
Fig. 2.22. Stabiliți în fereastra Setări Solver atunci când rezolvați sarcina de transport
Rămâne să faceți clic pe butonul "Rezolvați" și să obțineți planul optim de transport. Puteți analiza cât de diferit este planul optim față de distribuția uniformă propusă ca o opțiune inițială și cum au scăzut costurile de transport:
Fig. 2.23. Soluția problemei transportului
Parametrii care controlează activitatea solverului
Să luăm în considerare posibilitățile de gestionare a lucrării Solverului, setat în fereastra Opțiuni:
· Timp maxim (MaxTime) - limitează timpul alocat procesului de căutare a soluției. Valoarea prestabilită este de 100 de secunde, ceea ce este de obicei suficient pentru sarcinile la scară mică, cu aproximativ 10 constrângeri. Pentru probleme de dimensiuni mari, această valoare ar trebui să fie mărită.
· Numărul maxim de iterații (iterații) este un alt mod de a limita timpul de căutare prin setarea numărului maxim de iterații. Valoarea implicită este 100, dar acest număr poate fi mărit la 32767. Mai des, dacă nu se primește o soluție pentru 100 de iterații, există puține speranțe să se obțină creșterea acesteia. Este mai bine să încercați să modificați aproximația inițială și să porniți din nou procesul de căutare.
· Eroare relativă (Precision) - specifică precizia constrângerilor. Uneori este mai ușor să schimbați constrângerea prin împingerea limitei decât să încercați să îndepliniți constrângerile cu o precizie ridicată.
· Convergență (convergență) - este dată în fracție zecimală, mai mică decât unitatea, permițând pentru a opri procesul de căutare atunci când soluții de convergență la punct fix, atunci când modificarea relativă în ultimele 5 iterații nu depășesc o fracție predeterminată.
· Să presupunem modelul liniar - această casetă de validare trebuie activată atunci când funcția obiectivă și constrângerile sunt funcții liniare. Aceste informații suplimentare permit Solverului să simplifice procesul de găsire a unei soluții.
· Valori non-negative (presupunem non-negativ) - acest flag, puteți seta restricții privind variabilele care vor căuta soluții în intervalul de valori pozitive, fără a preciza restricțiile speciale la frontiera de jos.
· Afișați rezultatele iterării - căsuța care vă permite să activați un proces de căutare pas cu pas, afișând rezultatele fiecărei iterații pe ecran. În situații complexe, atunci când Solverul nu găsește automat o soluție, se recomandă să activați această casetă de selectare, deoarece uneori puteți găsi un punct din care procesul de căutare a fost evitat.
• Utilizați Scala de automatizare - caseta de selectare a scalei automate ar trebui să fie activată când scala valorilor variabilelor de intrare și a funcției și constrângerilor obiective este diferită, eventual în ordine de mărime. De exemplu, variabilele sunt specificate în bucăți, iar funcția obiectivă care specifică valoarea totală este măsurată în milioane de ruble.
· Eroare relativă (Toleranță) - este setată în procente. Această valoare este semnificativă doar pentru problemele cu constrângeri întregi. Solverul în astfel de probleme găsește mai întâi soluția optimă non-integer și apoi încearcă să găsească cel mai apropiat punct intreg, soluția în care diferă de cea optimă cu nu mai mult decât numărul de procente indicat de acest parametru. Dacă se găsește un astfel de punct, Solver raportează succesul. Cu o toleranță mare (implicit 5%), soluția cea mai bună poate fi pierdută, deși diferită de cea găsită de Solver în cadrul toleranței. Pentru sarcini întregi, toleranța are sens să se reducă, ceea ce am făcut atunci când am rezolvat problema transportului. Vreau din nou să acorde o atenție deosebită acestei trăsături de rezolvare a problemelor de programare întregi. Dacă valoarea parametrului de toleranță este setată la un nivel ridicat, Solverul se poate opri înainte de a nu găsi soluția cel mai bun întreg. Dacă îl luați mic, soluția cel mai bun întreg va diferi de soluția optimă non-integeră cu o valoare mai mare decât cea specificată de parametrul Toleranță. În acest caz, decizia se încheie în mod oficial cu eșec, deoarece soluția găsită nu satisface toate cerințele. Desigur, parametrul Toleranță joacă un rol de serviciu, iar Solverul "inteligent", după găsirea celei mai bune soluții întregi, ar trebui să anunțe că sa găsit o soluție, dar constrângerea de toleranță nu este îndeplinită. Acest lucru, totuși, nu se întâmplă. Încă vom întâlni această situație atunci când analizăm următoarea problemă.
· Salvați modelul - butonul de comandă; vă permite să deschideți o casetă de dialog unde puteți specifica numele modelului salvat. Este logic să utilizați această funcție când există mai multe modele pe foaia de lucru, deoarece singurul model este memorat automat.
· Load Model - permite încărcarea unuia dintre modelele stocate.
· Există câțiva parametri speciali care pot fi controlați prin modificarea procedurilor utilizate în procesul de căutare. Ar trebui să li se recurgă la situații dificile, când nu se poate găsi o soluție.
Articole similare
Trimiteți-le prietenilor: