Transportoppgave

Redegjørelse om transportproblemet

Transportproblemet (T-problemet) er et av de vanligste spesielle LP-problemene. Den første strenge uttalelsen av T-problemet tilhører F. Hitchcock, derfor kalles det i utenlandsk litteratur ofte Hitchcock-problemet.

Den første eksakte metoden for å løse T-problemet ble utviklet av L. V. Kantorovich og M. K. Gavurin.

Den generelle redegjørelsen for transportproblemet er å bestemme den optimale planen for transport av noe homogen last fra m utgangspunkt (fabrikker, varehus, baser osv.) i n reisemål (butikker). Samtidig er det fra hvert avgangspunkt (produksjon) mulig å transportere produktet til et hvilket som helst bestemmelsessted (forbruk). Som et optimalitetskriterium tas vanligvis enten minimumskostnaden for å transportere hele lasten, eller minimumstiden for levering.

Velge et optimalitetskriterium

Ved løsning av et transportproblem er valget av et optimalitetskriterium viktig. Som du vet, evaluering av økonomisk effektivitet omtrentlig plan kan bestemmes etter ett eller annet kriterium, som ligger til grunn for planberegningen. Dette kriteriet er en økonomisk indikator som karakteriserer kvaliteten på planen. Til dags dato er det ikke noe generelt akseptert enkelt kriterium som helhetlig tar hensyn til økonomiske faktorer. Ved løsning av et transportproblem brukes følgende indikatorer som et optimalitetskriterium i ulike tilfeller:

1) Volumet av transportarbeid (kriterium - avstand i t / km). Minimum kjørelengde er nyttig for å estimere reiseplaner fordi reiseavstanden er enkelt og nøyaktig bestemt for enhver retning. Derfor kan ikke kriteriet løse transportproblemer som involverer mange transportformer. Det er vellykket brukt til å løse transportproblemer for veitransport. Ved utvikling av optimale ordninger for transport av homogene varer med biler.

2) Tariff for frakt av varer (kriterium - tariffer for fraktkostnader). Lar deg få en transportordning som er best når det gjelder selvbærende indikatorer for bedriften. Alle tilleggene, samt eksisterende innmatingstariffer, gjør det vanskelig å bruke.

3) Driftskostnader for transport av varer (kriterium - kostnaden for driftskostnader). Mer nøyaktig gjenspeiler transportøkonomien forskjellige typer transportere. Lar deg trekke rimelige konklusjoner om muligheten for å bytte fra en transportmåte til en annen.

4) Leveringsbetingelser for varer (kriterium - tidskostnaden).

5) Reduserte kostnader (som tar hensyn til driftskostnader, avhengig av størrelsen på bevegelsen og kapitalinvestering i det rullende materiellet).

6) Reduserte kostnader (som tar hensyn til de fulle driftskostnadene ved kapitalinvesteringer for bygging av anlegg i det rullende materiellet).

,

hvor er driftskostnaden,

Estimert,

Kapitalinvesteringer kommer per 1 tonn last i hele seksjonen,

T - reisetid,

C - prisen på ett tonn last.

Gir mulighet for en mer fullstendig vurdering av rasjonalisering ulike alternativer transportplaner, med et ganske fullstendig uttrykk kvantitativt-samtidig påvirkning av flere økonomiske faktorer.

La oss vurdere et transportproblem, hvis optimalitetskriteriet er minimumskostnaden for å transportere hele lasten. La oss betegne med tariffene for transport av en lastenhet fra i-te avgangspunkt til j-te element destinasjon, gjennom - lagre av last i i-te ledd avgangspunkt, gjennom er etterspørselen etter last på jøde destinasjon, og gjennom er antall enheter med last som transporteres fra i-te origo til j-destinasjon. Da består den matematiske formuleringen av oppgaven i å bestemme minimumsverdien til funksjonen

under forhold

(2)

(3)

(4)

Siden variablene tilfredsstille systemene lineære ligninger(2) og (3) og betingelsen om ikke-negativitet (4), deretter sikres eksport av tilgjengelig last fra alle avgangspunkter, levering av den nødvendige mengden last til hver av destinasjonene, og returforsendelser er sikret også utelukket.

Dermed er T-problemet et LP-problem med m*n antall variabler, og m+n antall restriksjoner - likheter.

Åpenbart er den totale tilgjengeligheten av last fra leverandører lik , og det totale behovet for last på destinasjoner er lik enheter. Dersom den totale etterspørselen etter last på destinasjoner er lik lastebeholdningen ved opprinnelse, dvs.

da kalles modellen for et slikt transportproblem lukket eller balansert.

Det er en rekke praktiske problemer der balansevilkåret ikke er oppfylt. Slike modeller kalles åpen. Mulige to tilfeller:

I det første tilfellet er full tilfredsstillelse av etterspørselen umulig..

Et slikt problem kan reduseres til et ordinært transportproblem som følger. Ved overskudd av etterspørsel i forhold til lager, dvs. en fiktiv ( m+1) - th startpunkt med lastebeholdning og tariffer antas å være null:

Da kreves det å minimere

under forhold

Vurder nå det andre tilfellet.

Tilsvarende, for , en fiktiv ( n+1) – den destinasjonen med behov og de tilsvarende tariffer anses som lik null:

Da kan det tilsvarende T-problemet skrives som følger:

Minimer

under forhold:

Dette reduserer problemet til et ordinært transportproblem, fra den optimale planen som den optimale planen for det opprinnelige problemet er oppnådd.

I fremtiden vil vi vurdere en lukket modell av transportproblemet. Hvis modellen for et spesifikt problem er åpen, omskriver vi, ut fra det ovenstående, tabellen over betingelser for problemet slik at likhet (5) er tilfredsstilt.

I noen tilfeller må du spesifisere at produkter ikke kan transporteres langs noen ruter. Deretter settes transportkostnadene langs disse rutene slik at de overstiger de høyeste kostnadene ved mulig transport (for å gjøre det ulønnsomt å bære på utilgjengelige ruter) - når man løser problemet til et minimum. Til det maksimale er det omvendt.

Noen ganger er det nødvendig å ta hensyn til at kontrakter for faste forsyningsvolumer inngås mellom noen ekspedisjonssteder og noen forbrukssteder, da er det nødvendig å utelukke volumet av garantert forsyning fra videre vurdering. For å gjøre dette trekkes det garanterte forsyningsvolumet fra følgende verdier:

fra beholdningen til det respektive ekspedisjonsstedet;

· fra behovene til den tilsvarende destinasjonen.

Eksempel.

Fire virksomheter av dette økonomisk region Tre typer råvarer brukes til å produsere produkter. Råvarebehovet til hvert av foretakene er lik henholdsvis 120, 50, 190 og 110 enheter. Råvarene er konsentrert på tre mottakssteder, og lagrene er henholdsvis lik 160, 140, 170 enheter. Råvarer kan leveres til hver av foretakene fra et hvilket som helst tidspunkt for mottak. Fraktpriser er kjente verdier og er gitt av matrisen

Lag en transportplan der de totale transportkostnadene er minimale.

Løsning. La oss betegne med antall enheter av råvarer som transporteres fra det i-te punktet for mottaket til det j-te foretaket. Da er betingelsene for levering og eksport av nødvendige og tilgjengelige råvarer sikret ved å oppfylle følgende likheter:

(6)

Med denne planen transport, vil de totale transportkostnadene være

Dermed består den matematiske formuleringen av dette transportproblemet i å finne en slik ikke-negativ løsning på systemet med lineære ligninger (6), der objektivfunksjonen (7) tar minimumsverdien.

Ved løsning av et transportproblem er valget av et optimalitetskriterium viktig. Som du vet, kan evalueringen av den økonomiske effektiviteten til en eksemplarisk plan bestemmes av et eller annet kriterium, som er grunnlaget for å beregne planen. Dette kriteriet er en økonomisk indikator som karakteriserer kvaliteten på planen. Til dags dato er det ikke noe generelt akseptert enkelt kriterium som helhetlig tar hensyn til økonomiske faktorer. Ved løsning av et transportproblem brukes følgende indikatorer som et optimalitetskriterium i ulike tilfeller:

1) Volumet av transportarbeid (kriterium - avstand i t / km). Minimum kjørelengde er nyttig for å estimere reiseplaner fordi reiseavstanden er enkelt og nøyaktig bestemt for enhver retning. Derfor kan ikke kriteriet løse transportproblemer som involverer mange transportformer. Det er vellykket brukt til å løse transportproblemer for veitransport. Ved utvikling av optimale ordninger for transport av homogene varer med biler.

2) Tariff for frakt av varer (kriterium - tariffer for fraktkostnader). Lar deg få en transportordning som er best når det gjelder selvbærende indikatorer for bedriften. Alle tilleggene, samt eksisterende innmatingstariffer, gjør det vanskelig å bruke.

3) Driftskostnader for transport av varer (kriterium - kostnaden for driftskostnader). Den gjenspeiler mer nøyaktig kostnadseffektiviteten til transport med ulike transportformer. Lar deg trekke rimelige konklusjoner om muligheten for å bytte fra en transportmåte til en annen.

4) Leveringsbetingelser for varer (kriterium - tidskostnaden).

5) Reduserte kostnader (som tar hensyn til driftskostnader, avhengig av størrelsen på bevegelsen og kapitalinvestering i det rullende materiellet).

6) Reduserte kostnader (som tar hensyn til de fulle driftskostnadene ved kapitalinvesteringer for bygging av anlegg i det rullende materiellet).

,

hvor er driftskostnaden,

Estimert,

Kapitalinvesteringer kommer per 1 tonn last i hele seksjonen,

T - reisetid,

C - prisen på ett tonn last.

Lar deg evaluere rasjonaliseringen av forskjellige alternativer for transportplaner mer fullstendig, med et ganske fullstendig uttrykk for den kvantitative og samtidige påvirkningen av flere økonomiske faktorer.

La oss vurdere et transportproblem, hvis optimalitetskriteriet er minimumskostnaden for å transportere hele lasten. La oss angi gjennom tariffene for transport av en lastenhet fra det i-te avgangspunktet til det j-te bestemmelsesstedet, gjennom - beholdningen av last ved det i-te avgangspunktet, gjennom - etterspørselen etter last på den j-te destinasjonen, og gjennom - antall enheter med last som transporteres fra den i-de opprinnelsen til den j-de destinasjonen. Da består den matematiske formuleringen av oppgaven i å bestemme minimumsverdien til funksjonen

under forhold

(2)

(3)

(4)

Siden variablene tilfredsstille systemene med lineære ligninger (2) og (3) og ikke-negativitetsbetingelsen (4), så er eksporten av den tilgjengelige lasten fra alle avgangspunkter, leveringen av den nødvendige mengden last til hver av destinasjonene sikret, og returtransport er også utelukket.

Dermed er T-problemet et LP-problem med m*n antall variabler, og m+n antall restriksjoner - likheter.

Åpenbart er den totale tilgjengeligheten av last fra leverandører lik , og det totale behovet for last på destinasjoner er lik enheter. Dersom den totale etterspørselen etter last på destinasjoner er lik lastebeholdningen ved opprinnelse, dvs.

da kalles modellen for et slikt transportproblem lukket eller balansert.

Det er en rekke praktiske problemer der balansevilkåret ikke er oppfylt. Slike modeller kalles åpen. Mulige to tilfeller:

I det første tilfellet er full tilfredsstillelse av etterspørselen umulig..

Et slikt problem kan reduseres til et ordinært transportproblem som følger. Ved overskudd av etterspørsel i forhold til lager, dvs. en fiktiv ( m+1) - th startpunkt med lastebeholdning og tariffer antas å være null:

Da kreves det å minimere

under forhold

Vurder nå det andre tilfellet.

Tilsvarende, for , en fiktiv ( n+1) – den destinasjonen med behov og de tilsvarende tariffer anses som lik null:

Da kan det tilsvarende T-problemet skrives som følger:

Minimer

under forhold:

Dette reduserer problemet til et ordinært transportproblem, fra den optimale planen som den optimale planen for det opprinnelige problemet er oppnådd.

I fremtiden vil vi vurdere en lukket modell av transportproblemet. Hvis modellen for et spesifikt problem er åpen, omskriver vi, ut fra det ovenstående, tabellen over betingelser for problemet slik at likhet (5) er tilfredsstilt.

I noen tilfeller må du spesifisere at produkter ikke kan transporteres langs noen ruter. Deretter settes transportkostnadene langs disse rutene slik at de overstiger de høyeste kostnadene ved mulig transport (for å gjøre det ulønnsomt å bære på utilgjengelige ruter) - når man løser problemet til et minimum. Til det maksimale er det omvendt.

Noen ganger er det nødvendig å ta hensyn til at kontrakter for faste forsyningsvolumer inngås mellom noen ekspedisjonssteder og noen forbrukssteder, da er det nødvendig å utelukke volumet av garantert forsyning fra videre vurdering. For å gjøre dette trekkes det garanterte forsyningsvolumet fra følgende verdier:

fra beholdningen til det respektive ekspedisjonsstedet;

· fra behovene til den tilsvarende destinasjonen.

Eksempel.

Fire bedrifter i denne økonomiske regionen bruker tre typer råvarer for produksjon av produkter. Råvarebehovet til hvert av foretakene er lik henholdsvis 120, 50, 190 og 110 enheter. Råvarene er konsentrert på tre mottakssteder, og lagrene er henholdsvis lik 160, 140, 170 enheter. Råvarer kan leveres til hver av foretakene fra et hvilket som helst tidspunkt for mottak. Fraktpriser er kjente verdier og er gitt av matrisen

Lag en transportplan der de totale transportkostnadene er minimale.

Løsning. La oss betegne med antall enheter av råvarer som transporteres fra det i-te punktet for mottaket til det j-te foretaket. Da er betingelsene for levering og eksport av nødvendige og tilgjengelige råvarer sikret ved å oppfylle følgende likheter:

(6)

Med denne planen transport, vil de totale transportkostnadene være

Dermed består den matematiske formuleringen av dette transportproblemet i å finne en slik ikke-negativ løsning på systemet med lineære ligninger (6), der objektivfunksjonen (7) tar minimumsverdien.

Løsning av transportproblemet

Hovedtrinnene for å løse transportproblemet:

1. Finn en innledende gjennomførbar plan.

2. Velg fra ikke-grunnleggende variabler den som skal introduseres i grunnlaget. Hvis alle ikke-grunnleggende variabler tilfredsstiller optimalitetsbetingelsene, fullfør løsningen, ellers gå til neste. steg.

3. Velg en variabel som skal utledes fra grunnlaget, finn en ny grunnløsning. Gå tilbake til trinn 2.

Enhver ikke-negativ løsning av systemer med lineære ligninger (2) og (3) bestemt av matrisen , kalles transportoppgaveplanen. Referanseplanen (grunnleggende) for T-problemet er en av dets gjennomførbare, grunnleggende løsninger.

Vanligvis blir de første dataene for transportoppgaven registrert i form av en tabell.

Matrisen C kalles matrisen for transportkostnader, matrisen X som tilfredsstiller betingelsene for T-problemet (2) og (3) kalles transportplanen, og variablene kalles transport. Planen, der målfunksjonen er minimal, kalles optimal.

Antall variabler i transportproblemet med m avgangssteder og n destinasjoner er lik m*n, og antall ligninger i systemene (2) og (3) er m+n. Siden vi antar at betingelse (5) er oppfylt, er antallet lineært uavhengige ligninger lik m+n-1. Derfor kan grunnplanen for transportoppgaven ikke ha mer enn m+n-1 ikke-null ukjente.

Hvis i referansedesignet er antallet komponenter som ikke er null nøyaktig lik m+n-1, så er designet ikke-degenerert, og hvis mindre, så degenerert.

Som for ethvert lineært programmeringsproblem, er den optimale planen for transportproblemet også en basisplan.

Konstruksjon av en tillatt (referanse) plan i transportproblemet

I analogi med andre problemer med lineær programmering begynner løsningen av transportproblemet med konstruksjonen av en tillatt grunnplan. Det finnes flere metoder for å konstruere innledende grunnplaner for T-problemet. Av disse er de vanligste nordvesthjørnemetoden og minimumselementmetode.

Den enkleste måten å finne den på er basert på den såkalte nordvesthjørnemetoden. Essensen av metoden er den sekvensielle fordelingen av alle lagre som er tilgjengelige på det første, andre, etc. produksjonspunkt, i henhold til det første, andre, etc. forbrukspunkt. Hvert distribusjonstrinn reduseres til et forsøk på å fullstendig tømme lagrene ved neste produksjonspunkt eller til et forsøk på å tilfredsstille behovene ved neste forbrukspunkt. På hvert trinn q nåværende ufordelte reserver er angitt og i (q ), og nåværende udekkede behov - b j (q ) . Byggingen av en akseptabel utgangsplan, etter nordvesthjørnemetoden, starter fra øvre venstre hjørne av transportbordet, mens vi antar a i (0) = a i, b j (0) = b j . For neste celle i raden Jeg og kolonne j , vurderer vi verdiene av ikke-allokerte aksjer i Jeg -te produksjonspunkt og udekket behov j -th forbrukspunkt, hvorav minimum er valgt og tilordnet som transportvolumet mellom disse punktene: x i, j =min(a i (q) , b j (q) ) . Etter det reduseres verdiene av ikke-allokert lager og udekket etterspørsel i de respektive punktene med dette beløpet:

a i (q+1) = a i (q) - x i, j, b j (q+1) = b j (q) - x i, j

Åpenbart, på hvert trinn, er minst én av likestillingene oppfylt: og i (q+1) = 0 eller b j (q+1) = 0 . Hvis det første er sant, betyr dette at hele beholdningen til det i-te produksjonspunktet er oppbrukt, og det er nødvendig å fortsette til fordeling av beholdningen på produksjonspunktet i+1 , dvs. flytt til neste celle nedover i kolonnen. Hvis b j (q+1) = 0, Dette betyr at behovet for j -th punkt, hvoretter overgangen til cellen som ligger til høyre for linjen følger. Den nylig valgte cellen blir den gjeldende, og alle de oppførte operasjonene gjentas for den.

Basert på tilstanden til balansen mellom forsyninger og behov, er det ikke vanskelig å bevise at vi i et begrenset antall trinn vil få en godkjent plan. I kraft av samme betingelse kan antall trinn i algoritmen ikke være mer enn m+n-1 , så vil alltid forbli gratis (null) mn-(m+n-1) celler. Derfor er den resulterende planen grunnleggende. Det er mulig at den nåværende ikke-allokerte beholdningen på et eller annet mellomtrinn viser seg å være lik det nåværende udekkede behovet (a i (q) = b j (q)) . I dette tilfellet skjer overgangen til neste celle i diagonal retning (de nåværende produksjons- og forbrukspunktene endres samtidig), noe som betyr "tap" av en komponent som ikke er null i planen, eller, med andre ord, degenerasjonen av konstruert plan.

Et trekk ved en akseptabel plan konstruert etter nordvesthjørnemetoden er at den objektive funksjonen på den har en verdi som regel langt fra den optimale. Dette er fordi det ikke tar hensyn til verdiene c i, j . I denne forbindelse, i praksis, for å få den opprinnelige planen, brukes en annen metode - minimum element metode, hvor ved fordeling av trafikkmengder blir cellene med de laveste prisene okkupert først.

Et eksempel på å finne en grunnlinje

F=14 x 11 + 28 x 12 + 21 x 13 + 28 x 14 + 10 x 21 + 17 x 22 + 15 x 23 + 24 x 24 + 14 x 31 + 30 x 32 + 25 x 33 + 21 x 34

Den opprinnelige planen ble innhentet ved bruk av nordvesthjørnemetoden. Problemet er balansert (lukket).

Tabell 1

Kostnaden for transport under denne planen er: 1681:

F=14 *27 + 28* 0 + 21*0 + 28*0 + 10 *6 + 17 *13 + 15*1 + 24 *0 + 14 *0 + 30 *0 +25*26 + 21 *17 = 1681

Estimert arbeid nr. 4: TRANSPORTPROBLEM

Den generelle redegjørelsen for transportproblemet er å bestemme den optimale planen for transport av noe homogen last fra avgangspunkt (produksjon) til bestemmelsessted (forbruk). I dette tilfellet blir enten minimumskostnaden for å transportere hele lasten eller minimumstiden for leveringen vanligvis tatt som et optimalitetskriterium. La oss vurdere et transportproblem, hvis optimalitetskriteriet er minimumskostnaden for å transportere hele lasten. La oss angi gjennom tariffene for transport av en lastenhet fra -th avgangspunkt til -th destinasjon, gjennom - beholdningen av last ved -th avgangspunkt, gjennom - etterspørselen etter last ved - th destinasjon, og gjennom - antall enheter med last som transporteres fra -th punkt avgang til th destinasjon. Vanligvis blir de første dataene for transportoppgaven registrert i form av en tabell.

produksjon	Forbrukspoeng				produksjon
forbruker

La oss lage en matematisk modell av problemet.

(1)

under restriksjoner

Plan , der funksjonen (1) tar sin minimumsverdi, kalles optimal plan transportoppgave.

Betingelsen for løselighet av transportproblemet

Teorem: For løseligheten av transportproblemet er det nødvendig og tilstrekkelig at lagerbeholdningen av last ved avgangspunktene er lik etterspørselen etter last på destinasjonene, dvs. at likestillingen

Modellen for et slikt transportproblem kalles lukket, eller lukket, eller balansert, ellers heter modellen åpen.

I tilfellet legges en dummy inn - destinasjon med behov ; tilsvarende når et fiktivt utgangspunkt med en lastereserve legges inn og de tilsvarende tariffer anses som lik null: . På denne måten reduseres problemet til det vanlige transportproblemet. I fremtiden vil vi vurdere en lukket modell av transportproblemet.

Antall variabler i transportproblemet med avgangs- og destinasjonssteder er , og antall ligninger i systemet (2)-(4) er . Siden vi antar oppfyllelsen av betingelse (5), er antallet lineært uavhengige ligninger . Derfor kan referansedesignet ikke ha mer enn null ukjente. Hvis antallet komponenter som ikke er null i grunnplanen er nøyaktig lik , kalles planen ikke-degenerert, og hvis mindre, så degenerert.

Bygge den første grunnlinjen

Det er flere metoder for å bestemme grunnlinjen: nordvestre hjørne (diagonal metode), metode laveste kostnad (minimumselement), metode dobbel preferanse og metode Vogel-tilnærminger.

La oss kort vurdere hver av dem.

1. Nordvesthjørnemetoden. Ved å finne grunnlinjen, i hvert trinn, vurderes den første av de gjenværende opprinnelsene og den første av de gjenværende destinasjonene. Utfylling av cellene i tilstandstabellen starter fra øvre venstre celle for det ukjente ("nordvestlige hjørnet") og slutter med cellen for det ukjente, dvs. som et diagonalt bord.

2. Laveste kostnadsmetode. Essensen av metoden ligger i det faktum at den minste er valgt fra hele kostnadstabellen og i cellen som tilsvarer den, den minste av tallene og er plassert, deretter enten raden som tilsvarer leverandøren, hvis beholdning er helt oppbrukt, eller kolonnen som tilsvarer forbrukeren, hvis behov er unntatt fra vederlag er helt tilfredsstilt, eller både rad og kolonne, dersom leverandørens varelagre er oppbrukt og forbrukerens behov er tilfredsstilt. Fra resten av kostnadstabellen velges igjen den laveste kostnaden, og prosessen med plassering av beholdninger fortsettes inntil alle beholdninger er fordelt og krav er tilfredsstilt.

3. Dobbel preferansemetode. Essensen av metoden er som følger. I hver kolonne merker du cellen med den laveste kostnaden med et "√"-tegn. Deretter gjøres det samme i hver linje. Som et resultat er noen celler merket "√√". De inneholder minimumskostnaden, både etter kolonne og rad. Maksimalt mulig trafikkvolumer plasseres i disse cellene, hver gang ekskluderer de tilsvarende kolonnene eller radene fra vurdering. Deretter fordeles transporten mellom cellene merket med tegnet "√". I resten av tabellen er forsendelser fordelt til laveste kostnad.

4. Vogel tilnærmingsmetode. Når du bestemmer grunnplanen med denne metoden, ved hver iterasjon, i alle kolonner og alle rader, blir forskjellen mellom de to minimumsratene registrert i dem funnet. Disse forskjellene er lagt inn i linjen og kolonnen spesielt utpekt for dette i tabellen over forholdene for problemet. Blant disse forskjellene, velg maksimum. I raden (eller kolonnen) som denne forskjellen tilsvarer, fastsettes minimumstariffen. Cellen det er skrevet i fylles ut ved denne iterasjonen.

Definisjon av optimalitetskriteriet

Ved hjelp av de vurderte metodene for å konstruere den innledende referanseplanen kan man få en degenerert eller ikke-degenerert referanseplan. Den konstruerte planen av transportproblemet som et lineært programmeringsproblem kunne bringes til en optimal ved hjelp av simpleksmetoden. Men på grunn av omfanget av simplekstabeller som inneholder tp ukjent, og en stor mengde beregningsarbeid for å oppnå den optimale planen ved å bruke mer enkle metoder. Den mest brukte metoden for potensialer (modifisert distribusjonsmetode).

Potensiell metode.

Metoden for potensialer lar deg bestemme, med utgangspunkt i en grunnleggende transportplan, for å bygge en løsning på transportproblemet i et begrenset antall trinn (iterasjoner).

Det generelle prinsippet for å bestemme den optimale planen for et transportproblem ved hjelp av denne metoden ligner prinsippet for å løse et lineært programmeringsproblem ved bruk av simpleksmetoden, nemlig: først blir en referanseplan for transportproblemet funnet, og deretter blir den suksessivt forbedret til en optimal plan er oppnådd.

La oss lage et dobbelt problem

1., - noen

3.

La det være en plan

Teorem(optimalitetskriteriet): For at den gjennomførbare transportplanen i transportproblemet skal være optimal, er det nødvendig og tilstrekkelig at det finnes slike tall , , at

Hvis en. (7)

tall og kalles potensialene til henholdsvis opprinnelses- og bestemmelsesstedene.

Det formulerte teoremet gjør det mulig å konstruere en algoritme for å finne en løsning på transportproblemet. Den består av følgende. La en av metodene omtalt ovenfor finne en referanseplan. For denne planen, hvor det er grunnleggende celler, er det mulig å bestemme potensialene og slik at betingelse (6) er oppfylt. Siden system (2)-(4) inneholder ligninger og ukjente, kan en av dem settes vilkårlig (for eksempel likestilles med null). Deretter bestemmes de gjenværende potensialene fra ligningene (6), og verdiene beregnes for hver av de frie cellene. Hvis det viser seg at , så er planen optimal. Hvis minst én ledig celle, så er planen ikke optimal og kan forbedres ved å overføre langs syklusen som tilsvarer denne frie cellen.

syklus i tabellen over betingelser for transportproblemet kalles en brutt linje, hvis toppunkter er plassert i de okkuperte cellene i tabellen, og koblingene langs radene og kolonnene, og ved hvert toppunkt i syklusen er det nøyaktig to koblinger, hvorav den ene er i raden og den andre i kolonnen. Hvis polylinjen som danner syklusen skjærer hverandre, er ikke selvskjæringspunktene hjørner.

Planforbedringsprosessen fortsetter inntil vilkårene (7) er oppfylt.

Et eksempel på løsning av et transportproblem.

En oppgave. Fire baser A 1 , A 2 , A 3 , A 4 mottok en homogen last i følgende mengde: a 1 tonn - til base A 1 , og 2 tonn - til base A 2 , og 3 tonn - til base A 1 3 og 4 tonn - til basen A 4. Den mottatte lasten må transporteres til fem punkter: b 1 tonn - til base B 1, b 2 tonn - til base B 2, b 3 tonn - til base B 3, b 4 tonn - til base B 4, b 5 tonn - til base B5. Avstander mellom destinasjoner vises i avstandsmatrisen.

avgangspunkter	reisemål
behov

Kostnaden for transport er proporsjonal med mengden last og avstanden som denne lasten transporteres over. Planlegg transport slik at totalkostnaden deres er minimal.

Løsning. La oss sjekke balansen i transportproblemet, for dette er det nødvendig at

, .

1. Løs problemet ved hjelp av diagonalmetoden eller nordvesthjørnemetoden.

Prosessen med å skaffe en plan kan ordnes i form av en tabell:

avgangspunkter

Det er nødvendig å skille mellom optimaliseringskriteriet og indikatorene for optimaliteten til godstransportplaner. Optimaliseringskriteriet bør gjenspeile essensen av den nasjonale økonomiske tilnærmingen til valget, med tanke på strategien økonomisk politikk stater på transportområdet. Valget av optimaliseringsindikatorer som reflekterer ulike aspekter ved det globale økonomiske optimaliseringskriteriet er en vanskelig oppgave.

Alle transportoppgaver med optimal tilknytning av destinasjoner til forgiftningspunkter, som praktisk talt implementeres i optimale ordninger for laststrømmer, løses i form av transportavstand basert på minimum lastomsetning. Objektfunksjonen Fc til transportproblemet har følgende form:

Fс = min хij lij, (1)

hvor m, n - antall avgangspunkter og destinasjon, henholdsvis;

хij - mengden godstrafikktransport for hver korrespondanse mellom avgangspunktene og destinasjonen, t;

lij - transportavstand for hver korrespondanse av lastestrømmen, km.

Som et resultat av forskning utført av I. V. Belov, ble det bevist at optimaliseringen av planer for transport av varer til et minimum av tonnkilometer ikke gjenspeiler hovedkarakteristikkene til det nasjonale økonomiske kriteriet om optimalitet og derfor ikke gjør det mulig å oppnå en virkelig optimal plan.

Den korteste avstanden som indikator på optimalitet er åpenbart uegnet for å optimalisere godstransportplaner for ulike samvirkende transportformer, dvs. ved kompilering av komplekse optimale ordninger for laststrømmer på nettverket forskjellige typer kommunikasjonsmåter.

Når du optimaliserer godstransportplaner, er den korteste kostnadsretningen heller ikke alltid den mest lønnsomme. Poenget er at mengden av kostnader i transportretningene ikke bare påvirkes av avstanden (rekkevidden), men også av en rekke andre operasjonelle, tekniske og sosioøkonomiske faktorer. Omfattende indikatorer som den beste måten alle de viktigste egenskapene til det nasjonale økonomiske kriteriet for optimalisering kan reflekteres i utviklingen av godstransportplaner, er kostnadsindikatorer. Bruken deres til å løse tsamsvarer fullt ut med moderne krav for å forbedre kvaliteten på planlegging og regulering av transport.

I samsvar med det grunnleggende optimeringskonseptet, begrunnet av MIIT, i nærvær av reserver av gjennomstrømning og bæreevne, er det mer økonomisk hensiktsmessig å bruke minimumsdriftskostnader avhengig av trafikkvolumet, dvs. minimumskostnad for transport i form av avhengige kostnader. Den objektive funksjonen til transportoppgaven vil i dette tilfellet se slik ut:

Fс = min хij С fabrikk ij, (2)

hvor C head ij er kostnaden for transport av varer for hver korrespondanse av lastestrømmen i form av avhengige kostnader, c / t.

I samsvar med overgangskonseptet for optimalisering i fravær av reserver for gjennomstrømning og bæreevne, er kostnadsindikatorene for gjeldende transportplanlegging også uakseptable. Optimaliseringsproblemet i dette tilfellet bør ikke løses for et minimum av nåværende kostnader, men for et maksimum av resultater i nivået for å møte produksjonsbehovene i transport. Disse målene oppfylles best av optimaliseringsindikatoren - minimumstiden for levering av varer, dvs.

Fс = min хij tij, (3)

hvor tjj er tidspunktet for levering av varer for hver korrespondanse av lastestrømmen, h.

Denne optimalitetsindikatoren, som er enkel, oppfyller best betingelsene for å optimalisere transporten av bedervelige varer, siden den samtidig gir et minimum av nasjonale økonomiske kostnader (inkludert tap av varer) under transport.

I sammenheng med overgangen fra transport til markedsrelasjoner, optimalisering av transportplaner basert på minimumstariffavgiftene, når den objektive funksjonen har formen

Fс = min хij С tar ij, (4)

hvor C tar ij er den lønnsomme tollsatsen for transport av varer for hver korrespondanse av lastestrømmen, k / t.

Tidligere ble det antatt at planen for minimum tonn-kilometer og planen for minimumstariffavgifter sammenfaller, siden fraktrater er basert på prinsippet om korteste transportavstander. Men dette utsagnet er ikke helt sant, siden tariffgebyret belastes hver gang ikke for en bestemt korteste transportavstand, men for gjennomsnittlig avstand til en gitt tariffsone. Tariffbelter, spesielt på lange avstander, endres i et bredt spekter.

Det er åpenbart at med den mulige og hensiktsmessige territorielle differensieringen av tariffer under markedsforhold, så vel som med deres dypere differensiering avhengig av transportkvalitetsnivået, vil de optimale transportplanene for et minimum av tonnkilometer og et minimum av tariffgebyrer. ikke lenger sammenfaller.

En annen viktig omstendighet bør tas i betraktning. Optimalisering av transportforbindelser til et minimum av tariffer betyr minimering av transportinntekter, noe som kan påvirke inntjeningen og lønnsomheten negativt, dvs. om transportens selvbærende interesser. Noen eksperter hevder at optimalisering av transportplaner for denne indikatoren generelt er uakseptabel, siden den bevisst setter transport i en ulik økonomisk situasjon sammenlignet med andre sektorer av økonomien. Det er en alvorlig innvending mot dette argumentet. Transportinntektene er samtidig tarifftransportkostnadene til den nasjonale økonomien, for økonomien som vi hele tiden må strebe etter, eliminere ulike typer irrasjonell transport og de uproduktive kostnadene forbundet med dem. Derfor, i sammenheng med utviklingen av markedsrelasjoner, bør optimalisering av transportplaner for et minimum av tariffgebyrer ha et bredere omfang. Men samtidig må det gå fra transportfeltet som sådan til logistikkfeltet som en optimalisering av forsyningsplanene.

De gitte kostnadene som en indikator på optimalitet kan brukes til å løse transportproblemer på nettverket av kommunikasjonsruter for forskjellige samvirkende transportformer under betingelsene for både nåværende og langsiktig planlegging og regulering av arbeid, så vel som på en type transport for langsiktige betingelser for planlegging og regulering av arbeid med utvikling av gjennomstrømming . Den objektive funksjonen til den optimale planen her kan uttrykkes på to måter: uten å ta hensyn til kostnadene for fraktmassen i transitt, hvis det ikke er betydelige forskjeller i leveringstidspunktet for varer ved å samhandle transportformer:

Fс = min хij (сij + En kij), (5)

tatt i betraktning kostnadene for lastmassen i transitt, når de samvirkende transportmåtene varierer betydelig i leveringstidspunktet for varer:

Fс = min хij (сij + Ен (кij + mij), (6)

hvor kij - spesifikk investering i rullende materiell og permanente enheter for hver korrespondanse av laststrømmen, til / t;

mij er enhetskostnaden for godsmassen underveis for hver korrespondanse av godstrafikken, c/t.

Når du velger kostnadsindikatorer med det formål å optimalisere transporten av varer, er det nødvendig å sikre størst mulig fullstendighet i disse indikatorene av alle deres bestanddeler av kostnader og tap som endres avhengig av endringer i forholdene i transportprosessen for spesifikk transport og økonomiske koblinger mellom varenes avgangspunkt og bestemmelsessted. Tilbake på slutten av 60- og 70-tallet ble det påpekt at det i nødvendige tilfeller, spesielt ved transport med deltagelse av forskjellige transportformer, er nødvendig å i tillegg ta hensyn til tapene knyttet til ikke-bevaring av lasten. Dette betydde de tilfellene der forskjeller i mengden tap etter transportmåte eller muligheter for å knytte forbrukere til leverandører på en gitt transportmåte i betydelig grad påvirker valget av en virkelig optimal transportplan.

Lignende vurderinger ble uttrykt av eksperter i forhold til problemet med å optimalisere landets drivstoff- og energibalanse og bestemme rollen til kull i den. Det ble hevdet at den riktige løsningen av optimaliseringsproblemet er mulig hvis dannelsen av økonomisk informasjon om drivstoff utføres på grunnlag av sammenlignbare og sammenlignbare indikatorer for alle stadier sosial produksjon etter identisk metodikk og på grunnlag av samme metodiske forutsetninger. I dette tilfellet er det spesielt viktig å nøyaktig ta hensyn til kostnadene forårsaket av tap av drivstoff under transport.

Drivstofftap er inkludert i kostnadene for transport kun gjennom olje- og gassrørledninger, samt kraftledninger. Tap av kull under transport blir ikke tatt i betraktning fullt ut og reflekteres som regel ikke i økonomiske beregninger. Dette fører til at ideer om effektivitetsgraden til en bestemt transportmåte blir forvrengt. For å fjerne forvrengningene forårsaket av uforlignelige kostnadsindikatorer ved optimalisering av landets drivstoff- og energibalanse, bør disse indikatorene ta hensyn til tapet av den tilsvarende lasten.

I noen arbeider av forskere-økonomer ble det bemerket at når man optimaliserer transport og økonomiske relasjoner, er det nødvendig å ta hensyn til ikke bare kvaliteten på transporten, men også kvaliteten på de mest transporterte nasjonale økonomiske produktene, deres forbrukeregenskaper. I dette tilfellet snakker vi om å reflektere i kostnadsindikatoren for optimalitet, ikke bare tap av transporterte varer, men også forskjeller i deres sortiment og kvalitetssammensetning. Dette betyr at optimalisering av transport av utskiftbare produkter av forskjellig sortiment og kvalitet, med en passende vurdering av forbrukernes egenskaper (kilometerstand) bildekk, brennverdi på drivstoff, andel næringsstoffer i gjødsel, jern i malm etc.) vil gi en optimal plan som skiller seg vesentlig fra den optimale planen som er utarbeidet uten å ta hensyn til disse forskjellene.

Den økonomiske og matematiske modellen for optimaliseringsproblemet, tatt i betraktning forbrukeregenskapene til utskiftbare produkter, ble implementert i spesifikke løsninger, spesielt i arbeidet til NIIMS (forfattere E. P. Nesterov, V. A. Skvortsova, etc.). I arbeidet til MIIT ble det fastslått at i utviklingen av operative nåværende og potensielle optimale planer for transport med jernbanetransport, må kostnadsindikatorene for optimalitet nødvendigvis ta hensyn til tapet av mange varer, spesielt bedervelige, bulk og bulk. Ved løsning av komplekse transportproblemer med å optimalisere transport for en hvilken som helst periode og planlegging med deltakelse av to eller flere samvirkende transportformer, må tap inkluderes i kostnadsindikatorene for optimalitet for alle varegrupper i samsvar med klassifiseringen. Eventuelle forskjeller i forbrukeregenskaper og kvalitet til utskiftbare varer bør gjenspeiles gjennom deres tilsvarende priser i kostnadene for lastmassen under transport. Funksjonene til den optimale planen kan uttrykkes i generelle termer: uten å ta hensyn til kostnadene for lastmassen under transport

Fс = min хij (сij + Enkij + y pe ij), (7)

tar hensyn til kostnaden for lastmassen under transport

Fс = min хij (сij + Ен (кij + mij + y pe ij), (8)

hvor y pe ij er den spesifikke verdien av gjeldende tap av varer i form av verdi for hver korrespondanse av lastestrømmen, k / t.

Optimalisering av lasttransport, tatt i betraktning deres tap, kan praktisk talt bare utføres etter overgangen til utviklingen av enkle eller komplekse optimale ordninger for laststrømmer når det gjelder kostnadsindikatorer for optimalitet - nåværende og reduserte kostnader. En veldig viktig oppgave i dette tilfellet er forhåndsutarbeidelsen av pålitelig regulatorisk økonomisk informasjon for å beregne tap under transport av varer.

Ved transport av bedervelige varer er tapene deres som regel mye, og ofte flere ganger, høyere enn de faktiske transportkostnadene. Derfor ser det ut til å være mulig å optimalisere gjeldende og operasjonelle planer for transport av bedervelige varer basert på minimum strømtap med obligatorisk oppfyllelse av spesifiserte leveringstider. Det kan hevdes at den optimale planen for å minimere tap sammenfaller med den optimale planen for å minimere leveringstiden for bedervelige varer. Den objektive funksjonen til denne optimale planen er:

Fс = min xij y pe ij. (9)

Det bør imidlertid tas i betraktning at den praktiske bruken av kostnadsoptimalitetsindikatorer for å løse transportproblemer og utarbeide optimale ordninger for godsstrømmer er beheftet med store vanskeligheter. Faktum er at den foreløpige beregningen av individuelle kostnadsindikatorer er svært komplisert. Disse indikatorene er ustabile over tid på grunn av konstante endringer i forhold og faktorer som påvirker kostnadsbeløpet. De første dataene for å beregne de individuelle komponentene i kostnadsindikatorene for optimalitet gir ikke alltid den nødvendige påliteligheten til resultatene.

Et overskudd av bæreevne øker kostnadene ved transport og produksjonskostnadene. Kriteriet for optimalitet er foreslått for å akseptere minimumstapene på den ene siden - fra underbruk av rullende materiell, på den andre - tapet av mottakere fra utidig levering.

Enhver laststrøm er preget av et fireindeksnummer: produksjonsstedet, lastens forbrukspunkt, lastens klasse og tidspunktet for levering av lasten til forbrukeren. For å levere alle tilvirkede produkter fra produksjonsstedet til forbruksstedet, må transportens bæreevne ikke være mindre enn verdien av godstrafikken.

Det er kjent at bæreevnen til det rullende materiellet er en sannsynlighetsverdi, som påvirkes av mange faktorer: vei- og klimatiske forhold, type og alderssammensetning av det rullende materiellet, førerkvalifikasjoner, samsvar med produksjonen og teknisk grunnlag med kapasiteten av flåten osv. Derfor kan størrelsen på godstrafikken i visse øyeblikk overstige bæreevnen til det rullende materiellet og en del av lasten vil ikke bli levert til forbruksstedet i tide.

Følgelig er hovedbetingelsen for rettidig transport av varer til forbruksstedet overskuddet av lastekapasiteten til det rullende materiellet sammenlignet med godstrafikken.